BOJ 7576-トマト

トマト(7576)

完全なコード

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

typedef struct	t_node
{
	int		x, y, day;
	struct t_node	*next;
}		node;

node	*front, *rear;
int	**flag, **box;

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 d)
{
	node	*new;
	new = (node *)malloc(sizeof(node));
	new -> x = x;
	new -> y = y;
	new -> day = d;
	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	ret, tmpx, tmpy;

	while (front -> next != rear)
	{
		tmpx = front -> next -> x;
		tmpy = front -> next -> y;
		ret = front -> next -> day;
		pop();
		if (tmpx + 1 < M && flag[tmpy][tmpx + 1] == 0)
		{
			push(tmpx + 1, tmpy, ret + 1);
			flag[tmpy][tmpx + 1] = 1;
		}
		if (tmpx - 1 >= 0 && flag[tmpy][tmpx - 1] == 0)
		{
			push(tmpx - 1, tmpy, ret + 1);
			flag[tmpy][tmpx - 1] = 1;
		}
		if (tmpy + 1 < N && flag[tmpy + 1][tmpx] == 0)
		{
			push(tmpx, tmpy + 1, ret + 1);
			flag[tmpy + 1][tmpx] = 1;
		}
		if (tmpy - 1 >= 0 && flag[tmpy - 1][tmpx] == 0)
		{
			push(tmpx, tmpy - 1, ret + 1);
			flag[tmpy - 1][tmpx] = 1;
		}
	}
	return (ret);
}

int	main(void)
{
	int	N, M, day, tmpd;

	scanf("%d%d", &M, &N);
	flag = (int **)calloc(N, sizeof(int *));
	box = (int **)calloc(N, sizeof(int *));
	for (int i = 0; i < N; i++)
	{
		flag[i] = (int *)calloc(M, sizeof(int));
		box[i] = (int *)calloc(M, sizeof(int));
	}
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			scanf("%d", &box[i][j]);
			if (box[i][j] == -1)
				flag[i][j] = -1;
		}
	init_queue();
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (flag[i][j] == 0 && box[i][j] == 1)
			{
				push(j, i, 0);
				flag[i][j] = 1;
			}
	day = BFS(N, M);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (!flag[i][j])
				day = -1;
	printf("%d\n", day);
	for (int i = 0; i < N; i++)
	{
		free(flag[i]);
		free(box[i]);
	}
	free(flag);
	free(box);
	return (0);
}

コードの説明

前に使った迷路より、整理したようで汚くてたまらない.

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

typedef struct	t_node
{
	int		x, y, day;
	struct t_node	*next;
}		node;

node	*front, *rear;
int	**flag, **box;

ヘッダは標準I/Oライブラリ、C標準ユーティリティライブラリを使用します.
Q x値,y値を計算するには,数日かかる.

	scanf("%d%d", &M, &N);
	flag = (int **)calloc(N, sizeof(int *));
	box = (int **)calloc(N, sizeof(int *));
	for (int i = 0; i < N; i++)
	{
		flag[i] = (int *)calloc(M, sizeof(int));
		box[i] = (int *)calloc(M, sizeof(int));
	}
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			scanf("%d", &box[i][j]);
			if (box[i][j] == -1)
				flag[i][j] = -1;
		}
	init_queue();
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (flag[i][j] == 0 && box[i][j] == 1)
			{
				push(j, i, 0);
				flag[i][j] = 1;
			}
	day = BFS(N, M);

メイン関数はM(横方向の長さ)、N(縦方向の長さ)を受け入れ、グローバル変数flagとbox変数のすべてを初期化し、繰り返し文を使用してboxの値を入力します.-1を入力すると、flagの対応する値のみが-1に設定されます.
キューを作成し、キューに入ることができるすべての数(ボックスで1として表される場所)をキューに入れておき、BFSを実行して戻り値(トマトがすべて成熟するのに必要な日数)を1日で格納します.

BFS関数

int	BFS(int N, int M)
{
	int	ret, tmpx, tmpy;

	while (front -> next != rear)
	{
		tmpx = front -> next -> x;
		tmpy = front -> next -> y;
		ret = front -> next -> day;
		pop();
		if (tmpx + 1 < M && flag[tmpy][tmpx + 1] == 0)
		{
			push(tmpx + 1, tmpy, ret + 1);
			flag[tmpy][tmpx + 1] = 1;
		}
		if (tmpx - 1 >= 0 && flag[tmpy][tmpx - 1] == 0)
		{
			push(tmpx - 1, tmpy, ret + 1);
			flag[tmpy][tmpx - 1] = 1;
		}
		if (tmpy + 1 < N && flag[tmpy + 1][tmpx] == 0)
		{
			push(tmpx, tmpy + 1, ret + 1);
			flag[tmpy + 1][tmpx] = 1;
		}
		if (tmpy - 1 >= 0 && flag[tmpy - 1][tmpx] == 0)
		{
			push(tmpx, tmpy - 1, ret + 1);
			flag[tmpy - 1][tmpx] = 1;
		}
	}
	return (ret);
}

キューに必要な値がすべて入っている以上、キューから値を減算し、隣接するマトリクスをキューに入れる操作を繰り返します.
この作業が完了すると、flag配列で完熟可能なトマトは全て完熟1となり、トマトのない部分−1となり、近くで完熟したトマトが隣接しない部分BFSが終了しても0となる.

day = BFS(N, M);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (!flag[i][j])
				day = -1;
	printf("%d\n", day);
	for (int i = 0; i < N; i++)
	{
		free(flag[i]);
		free(box[i]);
	}
	free(flag);
	free(box);
	return (0);
}

繰り返し文を使用して配列全体をループします.0の場合、保存した日数ではなく-1に変更します.day를 출력が完了すると、割り当てられた配列を全て解除し、プログラムを終了する.