🔥

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 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

Source

from collections import deque

n = int(input())

for i in range(n):
	w, h = map(int ,input().split())
	_map = [list(input()) for _ in range(h)]
	dist = [[0 for _ in range(w)] for _ in range(h)]
	ans = w * h + 1
	q = deque()

	for _h in range(h):
		for _w in range(w):
			if(_map[_h][_w] == '@'):
				x = _h
				y = _w
				_map[_h][_w] = '.' # 빈 공간으로 초기화
			if(_map[_h][_w] == '*'):
				q.append([_h, _w, 1])
				_map[_h][_w] = '.' # 빈 공간으로 초기화
	q.append([x, y, -1]) # d(거리)가 양수이면 방문한 곳, 음수이면 방문하지 않은 곳

	while(True):
		if(len(q) == 0):
			break
		x, y, d = q.popleft()
		nd = 0
		if(d > 0):
			nd = d + 1
		else:
			nd = d - 1

		if(x < 0 or x >= h or y < 0 or y >= w or _map[x][y] != '.' or dist[x][y] != 0):
			continue
		if(d < 0 and (x == 0 or x == h - 1 or y == 0 or y == w - 1)):
			ans = min(ans, -d)
		dist[x][y] = d

		dx = [-1, 0, 1, 0]
		dy = [0, -1, 0, 1]

		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			q.append([nx, ny, nd])

	if(ans == (w * h + 1)):
		print("IMPOSSIBLE")
	else:
		print(ans)

참고