結果

問題 No.3 ビットすごろく
コンテスト
ユーザー C_kumo
提出日時 2019-01-16 09:24:25
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,993 bytes
コンパイル時間 1,006 ms
コンパイル使用メモリ 30,720 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 09:12:30
合計ジャッジ時間 1,359 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

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

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

char *visited;

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

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

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

	scanf("%hd",&n);

	visited = (char *)malloc(sizeof(char) * n);
	if (visited == NULL) {
		perror("visited malloc");
		exit(1);
	}
	visited[0] = 1;
	for (i=0;i<n;i++) visited[i] = 0;
	iniBoard(&b);
	
	que = iniQueue();	
	enqueue(que,b.walked,b.pos);

	ans = walking(n,que);

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

	freeQue(que);
	return 0;
}

Node *createNode(short 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,short 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)
{
	char i=0;

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

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

	char wNum;
	short ans;

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

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

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

	return ans;
}
0