[백준]4179 불!

문제

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

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

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

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

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

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

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

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

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

BFS문제입니다.

불이 번지는 문제는 이전에 풀었던 문제와 유사하지만,

이 문제는 불과 지훈이가 동시에 움직입니다.

먼저 불에 대해서 BFS를 수행하고,

지훈이에대해 BFS를 수행합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1}, INF = 987654321;

using namespace std;
int N, M, D, x;
char mp[1001][1001];
int v1[1001][1001], v2[1001][1001];
int main() {
	FAST;
	queue<pi>q1;
	queue<pi>q2;
	cin >> N >> M;
	REP(i, N)REP(j, M) {
		cin >> mp[i][j];
		if (mp[i][j] == 'J') {
			if (i == 1 || i == N || j == 1 || j == M) {
				cout << 1;
				return 0;
			}
			q1.push({ i,j });
		}
		if (mp[i][j] == 'F') {
			q2.push({ i,j });
			v2[i][j] = 1;
		}
	}
	while (!q2.empty()) {
		auto [y, x] = q2.front();
		q2.pop();
		rep(i, 4) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 1 && ny <= N && nx >= 1 && nx <= M && !v2[ny][nx] && mp[ny][nx] != '#') {
				q2.push({ ny,nx });
				v2[ny][nx] = v2[y][x] + 1;
			}
		}
	}
	while (!q1.empty()) {
		auto [y, x] = q1.front();
		q1.pop();
		rep(i, 4) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 1 && ny <= N && nx >= 1 && nx <= M && !v1[ny][nx] && mp[ny][nx] != '#' && (v1[y][x]+2 < v2[ny][nx] || !v2[ny][nx])) {
				q1.push({ ny,nx });
				v1[ny][nx] = v1[y][x] + 1;
				if (ny == 1 || ny == N || nx == 1 || nx == M) {
					cout << v1[ny][nx]+1;
					return 0;
				}
			}
		}
	}
	cout << "IMPOSSIBLE";
}