https://www.acmicpc.net/problem/4179
4179번: 불!입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문www.acmicpc.net
처음부터 풀이기 보였다.
모르는점은 불이랑 지훈이가 동시에도착하면 사냐 죽나였는데 죽는단다.
move 하나를 잘못입력해서 30여분 날렸다.
동시에 도착하면 죽으므로, 모든 불의 위치를 먼져 deque에 넣는다. 이때, (i,j,-1) 마지막값을 -1로해준다
그후 지훈이의 위치를 넣는다. 마지막 값에 시간을 넣을거므로 0으로 해준다.
이후 bfs를진행하며, 지훈이의 x좌표가 0 또는 R 지훈이의 y좌표가 0또는 C이면, 시간을 계산해주고 종료한다
or impossible
move를 잘 보자
import sysfrom collections import dequeinput=sys.stdin.readline
move=((-1,0),(1,0),(0,-1),(0,1))def bfs(fire,jihun): que=deque()
for f in fire: que.append(f) que.append(jihun) while que:
i,j,t=que.popleft() for a,b in move:
tmp_i,tmp_j=i+a,j+b
if 0<=tmp_i<R and 0<=tmp_j<C and arr[tmp_i][tmp_j]=='.':
if t==-1: que.append((tmp_i,tmp_j,t))
arr[tmp_i][tmp_j]='F' else:
if tmp_i==R-1 or tmp_i==0 or tmp_j==C-1 or tmp_j==0 :
# for k in arr: # print(k)
print(t+2) exit()
que.append((tmp_i,tmp_j,t+1))
arr[tmp_i][tmp_j]='J'
print("IMPOSSIBLE") R,C=map(int,input().split())
arr=[]for _ in range(R): arr.append(list(input().strip()))fire=[]
for i in range(R): for j in range(C): if arr[i][j]=='J':
arr[i][j]='@' jihun=((i,j,0))
if i==0 or j==0 or i==R-1 or j==C-1:
print(1) exit() elif arr[i][j]=='F':
fire.append((i,j,-1)) bfs(fire,jihun)