BOJ 2178-迷宫を探す

寻找迷宫(2178)

完全なコード

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

int	**maze, **flag;

typedef struct	_node
{
	int		x, y, cnt;
	struct _node	*next;
}		node;

node	*front, *rear;

void	init_queue(void)
{
	front = (node *)malloc(sizeof(node));
	rear = (node *)malloc(sizeof(node));

	front -> next = rear;
	rear -> next = rear;
}

void	push(int x, int y, int cnt)
{
	node	*new;

	new = (node *)malloc(sizeof(node));
	new -> x = x;
	new -> y = y;
	new -> cnt = cnt;
	if (front -> next == rear)
	{
		front -> next = new;
		new -> next = rear;
		rear -> next = new;
		return ;
	}
	rear -> next -> next = new;
	new -> next = rear;
	rear -> next = new;
}

void	pop(void)
{
	node	*curr;

	curr = front -> next;
	front -> next = curr -> next;
	free(curr);
}

int	BFS(int N, int M)
{
	int cnt = 0;
	push(1 ,1, cnt + 1);
	flag[1][1]++;
	while (front -> next != rear)
	{
		int	buf_x, buf_y;

		buf_x = front -> next -> x;
		buf_y = front -> next -> y;
		cnt = front -> next -> cnt;
		pop();
		if (buf_x == M && buf_y == N)
			break ;
		if (buf_x - 1 >= 1 && !flag[buf_y][buf_x - 1] && maze[buf_y][buf_x - 1])
		{
			push(buf_x - 1, buf_y, cnt + 1);
			flag[buf_y][buf_x - 1]++;
		}
		if (buf_x + 1 <= M && !flag[buf_y][buf_x +1] && maze[buf_y][buf_x + 1])
		{
			push(buf_x + 1, buf_y, cnt + 1);
			flag[buf_y][buf_x + 1]++;
		}
		if (buf_y - 1 >= 1 && !flag[buf_y - 1][buf_x] && maze[buf_y - 1][buf_x])
		{
			push(buf_x, buf_y - 1, cnt + 1);
			flag[buf_y - 1][buf_x]++;
		}
		if (buf_y + 1 <= N && !flag[buf_y + 1][buf_x] && maze[buf_y + 1][buf_x])
		{
			push(buf_x, buf_y + 1, cnt + 1);
			flag[buf_y + 1][buf_x]++;
		}
	}
	return (cnt);
}

int	main(void)
{
	int	M, N;

	init_queue();
	scanf("%d%d", &N, &M);
	maze = (int **)calloc(1, sizeof(int *) * (N + 1));
	flag = (int **)calloc(1, sizeof(int *) * (N + 1));
	for (int i = 0; i <= N; i++)
	{
		maze[i] = (int *)calloc(1, sizeof(int) * (M + 1));
		flag[i] = (int *)calloc(1, sizeof(int) * (M + 1));
	}
	for (int y = 1; y <= N; y++)
	{
		char	buf[101];
		scanf("%s", buf);
		for (int i = 0; i < M; i++)
			maze[y][i + 1] = buf[i] - '0';
	}
	printf("%d\n", BFS(N, M));
	for (int i = 0; i <= N; i++)
	{
		free(maze[i]);
		free(flag[i]);
	}
	free(maze);
	free(flag);
	free(front);
	free(rear);
	return (0);
}

typedef struct	_node
{
	int		x, y, cnt;
	struct _node	*next;
}		node;

Queueの構造

int	BFS(int N, int M)
{
	int cnt = 0;
	push(1 ,1, cnt + 1);
	flag[1][1]++;
	while (front -> next != rear)
	{
		int	buf_x, buf_y;

		buf_x = front -> next -> x;
		buf_y = front -> next -> y;
		cnt = front -> next -> cnt;
		pop();
		if (buf_x == M && buf_y == N)
			break ;
		if (buf_x - 1 >= 1 && !flag[buf_y][buf_x - 1] && maze[buf_y][buf_x - 1])
		{
			push(buf_x - 1, buf_y, cnt + 1);
			flag[buf_y][buf_x - 1]++;
		}
		if (buf_x + 1 <= M && !flag[buf_y][buf_x +1] && maze[buf_y][buf_x + 1])
		{
			push(buf_x + 1, buf_y, cnt + 1);
			flag[buf_y][buf_x + 1]++;
		}
		if (buf_y - 1 >= 1 && !flag[buf_y - 1][buf_x] && maze[buf_y - 1][buf_x])
		{
			push(buf_x, buf_y - 1, cnt + 1);
			flag[buf_y - 1][buf_x]++;
		}
		if (buf_y + 1 <= N && !flag[buf_y + 1][buf_x] && maze[buf_y + 1][buf_x])
		{
			push(buf_x, buf_y + 1, cnt + 1);
			flag[buf_y + 1][buf_x]++;
		}
	}
	return (cnt);
}

終了条件

アルゴリズム#アルゴリズム#