문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
#: 벽.: 지나갈 수 있는 공간J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int r, c;
cin >> r >> c;
string str[1002];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
queue<pair<int, int>> exodus;
queue<pair<int, int>> fire;
int fDist[1002][1002];
int jDist[1002][1002];
for(int i=0;i<r;i++) {
fill(fDist[i], fDist[i]+c, -1);
fill(jDist[i], jDist[i]+c, -1);
}
for(int i=0;i<r;i++) cin >> str[i];
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++){
if(str[i][j] == 'J') {
exodus.push({i, j});
jDist[i][j] = 0;
}
if(str[i][j] == 'F') {
fire.push({i, j});
fDist[i][j] = 0;
}
}
}
while(!fire.empty()) {
pair<int, int> curF = fire.front();
fire.pop();
for(int i=0;i<4;i++) {
int fx = curF.first + dx[i];
int fy = curF.second + dy[i];
// 불 움직이기
// 1) 불이 가지 못하는 곳
if(fx < 0 || fx >= r || fy < 0 || fy >=c) continue;
// 벽이거나 이미 갔던 곳
if(str[fx][fy] == '#' || fDist[fx][fy] >=0) continue;
fDist[fx][fy] = fDist[curF.first][curF.second] + 1;
fire.push({fx, fy});
}
}
while(!exodus.empty()) {
pair<int, int> curJ = exodus.front();
exodus.pop();
for(int i=0;i<4;i++) {
int jx = curJ.first + dx[i];
int jy = curJ.second + dy[i];
if(jx < 0 || jx >= r || jy < 0 || jy >=c) {
cout << jDist[curJ.first][curJ.second] + 1;
return 0;
}
// 지훈이 움직이기
// 1) 지훈이가 가지 못하는 곳
if(str[jx][jy] == '#' || jDist[jx][jy] >= 0) continue;
// 이미 fire가 다녀간 곳이거나, 도착한 시점에 불이 동시에 도착하거나, 혹은 자신보다 불이 더 빨리 도착하는 자리에 갈 수 없음.
if(fDist[jx][jy]!=-1 && fDist[jx][jy] <= jDist[curJ.first][curJ.second]+1) continue;
jDist[jx][jy] = jDist[curJ.first][curJ.second] + 1;
exodus.push({jx, jy});
}
}
cout << "IMPOSSIBLE";
return 0;
}