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

• 問題: No.3 ビットすごろく
• ユーザー: C_kumo
• 提出日時: 2019-01-15 02:43:44
• 言語: C (gcc 12.3.0)
• 結果: MLE
• 実行時間: -
• コード長: 2,691 bytes
• コンパイル時間: 1,442 ms
• コンパイル使用メモリ: 30,336 KB
• 実行使用メモリ: 812,928 KB
• 最終ジャッジ日時: 2024-06-23 09:47:11
• 合計ジャッジ時間: 3,628 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

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

ソースコード

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

#define MOVEMAX 32

typedef struct s_board {
	int walked;
	int pos;
} Board;

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

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

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

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

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

	scanf("%d",&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(int walked,int 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,int walked,int 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;
}

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

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

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

	int wNum,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;
}