🔥불!

BFS를 2번 돌리는 문제!🔥

'탈모 걸릴뻔했다.'

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	17718	4275	2912	22.160%

문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3

구현

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dist_fire[1001][1001];
int run[1001][1001];

string maze[1001];

int dx[]{ -1,1,0,0 };
int dy[]{ 0,0,-1,1 };

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int r, c;
	cin >> r >> c;
	queue<pair<int, int>> Q_fire;
	queue<pair<int, int>> Q_run;
	for (int i = 0; i < r; i++)
	{
		cin >> maze[i];
	}

	for(int i = 0 ; i < r; i ++)
		for (int j = 0; j < c; j++)
		{
			dist_fire[i][j] = -1;
			run[i][j] = -1;
		}

	for (int i = 0; i < r; i++)
	{
		int j = 0;
		for (auto& e : maze[i])
		{
			if (e == 'F')
			{
				Q_fire.push({i,j});
				dist_fire[i][j] = 0;
			}
			j++;
		}
	}

	for (int i = 0; i < r; i++)
	{
		int j = 0;
		for (auto& e : maze[i])
		{
			if (e == 'J')
			{
				Q_run.push({ i,j });
				run[i][j] = 0;
			}
			j++;
		}
	}
	//1st bfs

	while (!Q_fire.empty())
	{
		auto cur = Q_fire.front(); Q_fire.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if (maze[nx][ny] == '#' || dist_fire[nx][ny] >= 0) continue;
			Q_fire.push({ nx,ny });
			dist_fire[nx][ny] = dist_fire[cur.X][cur.Y] + 1;
		}

	}
	//2st bfs
	while (!Q_run.empty())
	{
		auto cur = Q_run.front(); Q_run.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];
			if (nx < 0 || nx >= r || ny < 0 || ny >= c)
			{
				cout << run[cur.X][cur.Y] + 1;
				return 0;
			}
			if (maze[nx][ny] == '#' || run[nx][ny] >= 0) continue;
			if (dist_fire[nx][ny] != -1 && dist_fire[nx][ny] <= run[cur.X][cur.Y] + 1) continue;
			Q_run.push({ nx,ny });
			run[nx][ny] = run[cur.X][cur.Y] + 1;
		}
	}
	cout << "IMPOSSIBLE";
	return 0;

}

• 코드가 좀 더러운 듯 하다.
• 정리 좀 해서 다시 올려야겠다...