fork download
copy 
  1. import sys
  2. from collections import deque
  3.  
  4. N = int(sys.stdin.readline())
  5. H = []
  6. W = []
  7. maps = []
  8. dx = [0,0,1,-1]
  9. dy = [1,-1,0,0]
  10. for _ in range(N):
  11.     h, w = map(int,sys.stdin.readline().split())
  12.     H.append(h)
  13.     W.append(w)
  14.     map_ = []
  15.     for _ in range(h):
  16.         map_.append(list(sys.stdin.readline())[:-1])
  17.     maps.append(map_)
  18.  
  19.  
  20. def solution(h,w, map_,prisoner_q):
  21.     global VISITED
  22.     finds = []
  23.     outs = []
  24.     while prisoner_q:
  25.         x, y, open_door = prisoner_q.pop()
  26.         for sx, sy in zip(dx,dy):
  27.             newx = x+sx
  28.             newy = y+sy
  29.             if validation(newx,newy,h,w):
  30.                 if not VISITED[newx][newy]:
  31.                     if map_[newx][newy]=='.':
  32.                         prisoner_q.appendleft((newx,newy,open_door))
  33.                         VISITED[newx][newy]=True
  34.                     elif map_[newx][newy]=='#':
  35.                         prisoner_q.appendleft((newx,newy,open_door+[(newx,newy)]))
  36.                         VISITED[newx][newy]=True
  37.                     elif map_[newx][newy]=='$':
  38.                         finds.append(open_door)
  39.             elif not validation(newx,newy,h,w):
  40.                 outs.append(open_door)
  41.  
  42.  
  43.  
  44.  
  45.     return finds, outs
  46.  
  47. def validation(x,y,h,w):
  48.     if x>=0 and y>=0 and x<h and y<w:
  49.         return True
  50.     return False
  51.  
  52. def find_prisoner(H,W, map_, prisoner_q):
  53.     global VISITED
  54.     for h in range(H):
  55.         for w in range(W):
  56.             if map_[h][w]=='$':
  57.                 prisoner_q.appendleft((h,w,[]))
  58.  
  59.  
  60.  
  61. for h, w, map_ in zip(H,W,maps):
  62.     prisoner_q1 = deque()
  63.     prisoner_q2 = deque()
  64.  
  65.     find_prisoner(h,w,map_, prisoner_q1)
  66.  
  67.     prisoner_q2.append(prisoner_q1.pop())
  68.     #죄수 1의 외부로 나가는 방법과 다른 죄수를 만나는 방법 서치
  69.     VISITED = [[False]*w for _ in range(h)]
  70.     VISITED[prisoner_q1[0][0]][prisoner_q1[0][1]]=True
  71.     finds1, outs1 = solution(h,w,map_,prisoner_q1)
  72.     #지나온 문들의 갯수를 저장
  73.     result1 = [len(set(find+out))for find in finds1 for out in outs1]
  74.  
  75.     #죄수 2의 외부로 나가는 방법과 다른 죄수를 만나는 방법 서치
  76.     VISITED = [[False]*w for _ in range(h)]
  77.     VISITED[prisoner_q2[0][0]][prisoner_q2[0][1]]=True
  78.     finds2, outs2 = solution(h,w,map_,prisoner_q2)
  79.     #지나온 문들의 갯수를 저장
  80.     result2 = [len(set(find+out))for find in finds2 for out in outs2]
  81.  
  82.     #외부로만 다니는게 가장 적을 수 있으므로 외부로 나가는 방법들만 저장
  83.     result3 = [len(set(out1+out2)) for out1 in outs1 for out2 in outs2]
  84.  
  85.     #가장 작은 수 print
  86.     print(min(result1+result2+result3))
  87.  
  88.  
  89.  
Runtime error #stdin #stdout #stderr 0.13s 23344KB
comments (?)
stdin
copy 
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********
stdout
copy 
4
0
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 65, in <module>
  File "./prog.py", line 56, in find_prisoner
IndexError: list index out of range
https://ideone.com/Z1olCr
language:
Python 3 (python  3.9.5)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!