[BFS] 움직이는 미로 탈출

예제 입력 1

........

........

........

........

........

........

........

........

예제 출력 1

1

예제 입력 2

........

........

........

........

........

........

##......

........

예제 출력 2

0

예제 입력 3

........

........

........

........

........

.#......

#.......

.#......

예제 출력 3

0

예제 입력 4

........

........

........

........

........

.#######

#.......

........

예제 출력 4

1

예제 입력 5

........

........

........

........

#.......

.#######

#.......

........

예제 출력 5

0

 

- 미로는 매초마다 벽이 아래로 움직이며 8초 뒤에는 모두 빈칸이 된다. 따라서 여기서는 벽이 움직인다고 해서 맵을 업데이트 할 필요는 없고, t초 후에 벽이되는지는 (r - t, c)를 체크하면 된다.

#include <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b))

constexpr int MAX_SIZE = 8;
constexpr int MAX_QUEUE_SIZE = (1000);

char map[MAX_SIZE][MAX_SIZE] = { 0 };
bool check[MAX_SIZE][MAX_SIZE][9] = { false, }; // 8초 후에는 모두 동일

int dR[] = { 0,0,1,-1,1,-1,1,-1,0 };
int dC[] = { 1,-1,0,0,1,1,-1,-1,0 };

class Point
{
public:
	int r;
	int c;
	int t;

	Point() { r = c = t = 0; }
	Point(int r, int c, int t) : r(r), c(c), t(t) {}

	bool isInBoundary()
	{
		return (r >= 0) && (r < MAX_SIZE) && (c >= 0) && (c < MAX_SIZE);
	}

	bool operator==(Point other)
	{
		return (r == other.r) && (c == other.c);
	}
};

template <typename T>
class Queue
{
private:
	int front;
	int rear;
	T items[MAX_QUEUE_SIZE];

public:
	Queue()
	{
		front = rear = 0;
	}

	void push(T item)
	{
		items[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = items[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty() { return front == rear; }
};
Queue<Point> q;


int main(void)
{
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			while (true)
			{
				scanf("%c", &map[i][j]);
				if (map[i][j] != '\n') break;
			}
		}
	}

	check[7][0][0] = true;
	Point init(7, 0, 0);
	Point target(0, 7, 0);

	q.push(init);

	while (!q.isEmpty())
	{
		Point now = q.pop();

		if (now == target)
		{
			printf("1\n");
			return 0;
		}

		for (int i = 0; i < 9; i++)
		{
			Point next(now.r + dR[i], now.c + dC[i], MIN(now.t + 1, 8));

			if (!next.isInBoundary()) continue;

			if (next.r - now.t >= 0 && map[next.r - now.t][next.c] == '#') continue; // 이동하려는 칸이 현재 벽
			if (next.r - next.t >= 0 && map[next.r - next.t][next.c] == '#') continue; // 이동한 뒤 칸이 벽이 되어버리면

			if (check[next.r][next.c][next.t] == false)
			{
				check[next.r][next.c][next.t] = true;
				q.push(next);
			}
		}
	}

	printf("0\n");

	return 0;
}