[백준/c++] 4179 불!

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

구현해야 할 조건

불의 이동이 우선! 불이 이동하고 지훈이가 이동하도록 하자! 이유는 지훈이가 이동한 자리가 불도 이동할 수 있는 자리라면 순서가 꼬이기 때문에! 불이 이동하고 지훈이가 이동을 해야 지훈이가 불이 오는 자리에 이동을 안 할수 있다 이점을 생각하고 문제를 해결하자

code

#include<iostream>
#include<queue>
#include<string>
#include<algorithm>

#define MAX 1010
using namespace std;

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

int r,c;
bool visited[MAX][MAX];
string map[MAX];

queue<pair<int,int> > Jihoon;
queue<pair<int,int> > Fire;
vector<pair<int,int> > f;

int bfs()
{
	for(int i = 0; i < f.size(); i++)
		Fire.push(f[i]);
		
	int res = 0;
	
	while(1)
	{
		if(Jihoon.empty())
			break;
			
		int fs = Fire.size();
		
		for(int i = 0; i < fs; i++){
			
			int x = Fire.front().second;
			int y = Fire.front().first;
			Fire.pop();
			
			for(int j = 0; j < 4; j++){
				
				int nx = x + dx[j];
				int ny = y + dy[j];
				
				if(0 <= nx && nx < c && 0 <= ny && ny < r){
					
					if(map[ny][nx] == '.' || map[ny][nx] == 'J')
					{
						map[ny][nx] = 'F';
						Fire.push({ny,nx});
						
					}
				}
			}
		}
		
		int curSize = Jihoon.size();
		
		for(int i = 0; i < curSize; i++){
			
			int x = Jihoon.front().second;
			int y = Jihoon.front().first;
			
			Jihoon.pop();
			
			if(x == 0 || y == 0 || x == c-1 || y == r-1)
				return res+1;
				
			for(int j = 0; j < 4; j++){
				
				int nx = x + dx[j];
				int ny = y + dy[j];
				
				if(!visited[ny][nx] && 0 <= nx && nx < c && ny < r && 0 <= ny){
					
					if(map[ny][nx] == '.')
					{
						map[ny][nx] = 'J';
						map[y][x] = '.';
						visited[ny][nx] = true;
						Jihoon.push({ny,nx});
						
					}
					
				}
				
			}
			
		}
		
		res++;
	}
	
	return -1;
	
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> r >> c;
	
	for(int i = 0; i < r; i++)
		cin >> map[i];
		
	for(int i = 0; i < r; i++){
		
		for(int j = 0; j < map[i].size(); j++){
			
			if(map[i][j] == 'J')
				Jihoon.push({i,j});
			if(map[i][j] == 'F')
				f.push_back({i,j});
		}
	}
	
	int res = bfs();
	
	if(res == -1)
		cout << "IMPOSSIBLE";
	else
		cout << res;
	
	return 0;
	
}