結果

問題 No.3 ビットすごろく
コンテスト
ユーザー C_kumo
提出日時 2019-01-15 02:43:44
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}
0