불

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	24021	6068	3859	23.174%

문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력1
2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

구현

#include <bits/stdc++.h>
using namespace std;

int testcase;
int w, h;
string graph[1000];
int fire_propagate[1002][1002];
int escape_time[1002][1002];
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);
	cin >> testcase;

	while (testcase--)
	{
		cin >> w >> h; //너비와 높이 입력받음

		for (int i = 0; i < h; i++)
		{
			fill(fire_propagate[i], fire_propagate[i] + w, -1);
			fill(escape_time[i], escape_time[i] + w, -1);
		}

		for (int i = 0; i < h; i++)
		{
			cin >> graph[i];
		}
		queue<pair<int, int>> fire_Q;
		queue<pair<int, int>> escape_Q;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (graph[i][j] == '*') { fire_Q.push({ i,j }); fire_propagate[i][j] = 0; }
				if (graph[i][j] == '@') { escape_Q.push({ i,j }); escape_time[i][j] = 0; }
			// 불(*) 위치를 큐에 넣고 방문처리
			// 사람위치를 큐에 넣고 방문처리
			}
		}
		
		// 1st bfs : 불 전파
		while (!fire_Q.empty())
		{
			auto cur = fire_Q.front(); fire_Q.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];
				if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue; // 다음이동위치가 맵 밖이면 방문안할거임
				if (graph[nx][ny] == '#' || fire_propagate[nx][ny] >= 0) continue;
				fire_Q.push({ nx,ny });
				fire_propagate[nx][ny] = fire_propagate[cur.first][cur.second] + 1;
			}
		}



		//2st bfs : 사람 탈출
		bool isesacpe = false;
		while ((!escape_Q.empty())&&(!isesacpe))
		{
			auto cur = escape_Q.front(); escape_Q.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];
				if (nx < 0 || nx >= h || ny < 0 || ny >= w)
				{
					// 맵 밖으로 나가면 탈출 성공인거지.
					cout << escape_time[cur.first][cur.second] + 1<< '\n';
					isesacpe = true;
					break;
				}
				if (graph[nx][ny] == '#' || escape_time[nx][ny] >= 0) continue;
				if (fire_propagate[nx][ny]!=-1 && fire_propagate[nx][ny] <= escape_time[cur.first][cur.second]+1) continue;
				escape_Q.push({ nx,ny });
				escape_time[nx][ny] = escape_time[cur.first][cur.second] + 1;
			}
		}
		if(!isesacpe)cout << "IMPOSSIBLE\n";
		
	}

	return 0;
}