아직 계정이 없으신가요? 회원가입

Dev. Talk

[GINI야 도와줘] 반례 부탁드리겠습니다..

회원사진i22024
44 views2023-01-04 06:41


import sys
input=sys.stdin.readline
from collections import deque
'''
지도는 R행과 C열. 
비어있는 칸은 ‘.’로 표시, 
소나기는 ‘*’로, 강은 ‘X’로 표시. 
태범이의 집은 ‘H’로 표현, 
태범이가 처음있던 세차장의 위치는 ‘W’로 표시.
매 분마다 태범이는 인접한 네 개의 칸(상, 하, 좌, 우)으로 이동할 수 있다. 
소나기는 매 분마다 인접한 네 개의 칸(상, 하, 좌, 우)으로 확산한다.
태범이는 소나기와 강을 지나지 못하며, 소나기는 강과 태범이의 집에 옮겨지지 않는다. 
(소나기는 강으로 가면 소멸)
'''
# 시간에 따른 소나기 확산
def timerain(maps):
    rainlist=[]
    # 현재 소나기가 존재하는 좌표를 담은 rainlist
    for j in range(R):
        for i in range(C):
            if maps[j][i]=="*":
                rainlist.append((j,i))
    # 확산 
    for j in range(R):
        for i in range(C):
            if len(rainlist)==0:
                return maps
            if maps[j][i]=="*" and (j,i) in rainlist:
                rainlist.remove((j,i))
                if 0<=j-1 and maps[j-1][i]==".":
                    maps[j-1][i]='*'
                if j+1<R and maps[j+1][i]==".":
                    maps[j+1][i]='*'
                if 0<=i-1 and maps[j][i-1]==".":
                    maps[j][i-1]='*'
                if i+1<C and maps[j][i+1]==".":
                    maps[j][i+1]='*'
    return maps
  
# BFS
def bfs(startX,startY,TFmaps,maps):
    q=deque()
    q.append((startY,startX))
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

    while q:
        maps=timerain(maps)
        ey,ex=q.popleft()
        for i in range(4):
            nx=ex+dx[i]
            ny=ey+dy[i]
            
            if 0<=nx<C and 0<=ny<R:
                if TFmaps[ny][nx]==0 and maps[ny][nx]=="H":
                    TFmaps[ny][nx]=TFmaps[ey][ex]+1
                    return TFmaps
                if TFmaps[ny][nx]==0 and maps[ny][nx]==".":
                    q.append((ny,nx))
                    TFmaps[ny][nx]=TFmaps[ey][ex]+1
        
    return TFmaps

#####입력 받고 bfs 실행 후 출력
R,C=map(int,input().split())
maps=[[] for _ in range(R)]
TFmaps=[[0]*C for _ in range(R)]
for r in range(R):
    K=input().strip()
    for k in range(len(K)):
         maps[r].append(K[k])
#print(maps)
#print(TFmaps)
# Start Point , End Point
for r in range(R):
    for c in range(C):
        if maps[r][c]=="W":
            startY=r 
            startX=c
        if maps[r][c]=="H":
            endY=r
            endX=c
            
TFmaps=bfs(startX,startY,TFmaps,maps)

if TFmaps[endY][endX]==0:
    print("FAIL")
else:
    print(TFmaps[endY][endX])