#310526 (C) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: C_kumo
• 提出日時: 2019-01-16 07:43:58
• 言語: C (gcc 12.3.0)
• 結果: WA
• 実行時間: -
• コード長: 2,735 bytes
• コンパイル時間: 409 ms
• コンパイル使用メモリ: 30,464 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-06-27 04:33:52
• 合計ジャッジ時間: 1,390 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	WA	-
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	1 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	1 ms; 5,376 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-

ソースコード

#include <stdio.h>
#include <stdlib.h>

#define MOVEMAX 16

typedef struct s_board {
	char walked;
	short pos;
} Board;

typedef struct s_node {
	Board b;
	struct s_node *next;
} Node;

typedef struct s_queue {
	Node *front;
	Node *rear;
} Queue;

Node *createNode(char walked,short pos,Node *next);
Queue *iniQueue(void);
void freeNode(Node *node);
void freeQue(Queue *que);
char isEmpty(Queue *que);
char enqueue(Queue *que,char walked,short pos);
Board dequeue(Queue *que, char *err);

void iniBoard(Board *b);
char walkNum(short a);
char walking(short n,Queue *que);

int main(void)
{
	short n;
	char ans;
	Queue *que;
	char err;
	Board b;

	scanf("%hd",&n);

	iniBoard(&b);
	
	que = iniQueue();	
	enqueue(que,b.walked,b.pos);

	ans = walking(n,que);

	printf("%d\n",ans);

	freeQue(que);
	return 0;
}

Node *createNode(char walked,short pos,Node *next)
{
	Node *node = malloc(sizeof(Node));
	if (node == NULL) {
		perror("node malloc");
		exit(1);
	}
	node->b.walked = walked;
	node->b.pos = pos;
	node->next = next;
	
	return node;
}

Queue *iniQueue(void)
{
	Queue *que = malloc(sizeof(Queue));
	if (que == NULL) {
		perror("que malloc");
		exit(1);
	}
	que->front = NULL;
	que->rear = NULL;

	return que;
}

void freeNode(Node *node)
{
	while (node != NULL) {
		Node *tmp = node->next;
		free(node);
		node = tmp;
	}
	return;
}

void freeQue(Queue *que)
{
	freeNode(que->front);
	free(que);
	return;
}

char isEmpty(Queue *que)
{
	if (que->front == NULL) return 1;
	else return 0;
}

char enqueue(Queue *que,char walked,short pos)
{
	Node *node = createNode(walked,pos,NULL);
	if (node == NULL) return 1;

	if (isEmpty(que) == 1) {
		que->front = node;
		que->rear = node;
	} else {
		que->rear->next = node;
		que->rear = node;
	}

	return 0;
}

Board dequeue(Queue *que, char *err)
{
	Board b;
	if (isEmpty(que)) {
		*err = 1;
		return b;
	}

	Node *node = que->front;
	b = node->b;

	que->front = node->next;
	free(node);

	if (que->front == NULL) que->rear = NULL;
	*err = 0;

	return b;
}

void iniBoard(Board *b)
{
	b->walked = 1;
	b->pos = 1;
	return;
}

char walkNum(short a)
{
	int i=0;

	while (1) {
		i += a % 2;
		if (a<=1) break;
		a = a / 2;
	}
	return i;
}

char walking(short n,Queue *que)
{
	Board b;
	char err;

	char wNum;
	int ans;

	ans = -1;
	while (1) {
		b = dequeue(que,&err);
		if (err==1) break;
		if (b.walked > MOVEMAX) break;

		if (b.pos == n) {
			ans = b.walked;
			break;
		}

		wNum = walkNum(b.pos);
		if (b.pos - wNum > 0) {
			err = enqueue(que,b.walked+1,b.pos-wNum);
			if (err == 1) {
				perror("enqueue -");
				break;
			}
		}
		if (b.pos + wNum <= n) {
			err = enqueue(que,b.walked+1,b.pos+wNum);
			if (err == 1) {
				perror("enqueue +");
				break;
			}
		}
	}

	return ans;
}