[day26] 코딩테스트 알고리즘 - 거리두기 확인하기 (feat.파이썬)

프로그래머스

lv.2 에서 난이도 상

🤟 문제 포인트

#A 대기실은 5개, 각 대기실은 5x5	[[5],[5],[5],[5],[5]]  5크기의 배열 * 5 를 다뤄야 한다.
#B 내가 갈 길이 이길이 아닌지 맞는지 알 수 없지만 알 수 없지만 알수없지만 문제를 풀어야 하네	O, X 인지 확인필요 O 인 경우  and 내가 방문안한 곳인지 1. 방문했다고 체크 2. 거리 저장 X 인 경우  아예 고려 안해도됨. 고려할 필요가 없어!!!!!!!!!
#C 맨해튼 거리 2 이하	위의 O인경우 저장한 distance 활용 distance > 1 이면 False  distance가 <=1 이면 True
#D 내가 갈 곳은 그럼 어떻게 구하느냐?	준비물 1. start 원소 원소 중에 P인 것을 찾아. 거기가 시작 포인트 2. 상하좌우 배열 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] 3. [start원소x + dx, start원소y +dy] 가 내가 갈 곳.

 

🤟 참고 코드

배열이 5개나 되기 때문에 우선 첫번째 줄만 분석해 보기로 했다. #A

주어진 자리에 대해 for문을 돌기 시작한다.

첫째줄 ["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"]에 대해서만 보도록 하자.

 

1. start 배열을 준비한다.

현재 시작 값이 어디인지 알려주는 배열이다.

각 줄에 대해 반복문을 돌며 값이 P라면 start에 현재 인덱스 값을 추가해준다.

[0]행의 POOOP 라면 start에는 [0,0],[0,4]값이 들어간다.

[1]행의 OXXOX 에는 P가 없기 때문에 패스한다.

[2]행의 OPXPX에서는 start에 [2,1],[2,3]이 추가된다. 따라서 현재의 start값은 [[0,0][0,4],[2,1],[2,3]]이 된다.

[3]행의 OOXOX 에는 P가 없기 때문에 패스한다.

[4]행의 POXXP 에서는 start에 [4,0],[4,4]가 추가된다.

결과적으로 start값은 [[0,0][0,4],[2,1],[2,3], [4,0],[4,4]]가 된다.

 

2. 위에서 준비한 start([[0,0][0,4],[2,1],[2,3], [4,0],[4,4]])의 반복문을 돌며 아래의 일을 수행한다.

2-1. 큐를 준비한다. 큐는 start의 요소들의 첫번째 값을 담아둔다. 첫번째 반복문에서 queue는 [0,0] 이다.

2-2. visited 와 distance 배열을 준비해준다. 각 배열은 5X5 배열이다. 첫번째 줄만 분석하기로는 했지만, 상관없다. visited에는 내가 방문한 곳인지를 기억해줄 것이고 distance에는 P로부터 방문한 곳의 거리를 기억해 줄 것이다.  visited[0,0]에 시작 값으로 1을 넣어준다. i. y,x 는 queue.popleft(), 즉 시작 위치이다. 현재의 queue값은 [0,0]이기 때문에 y = 0, x= 0이다.

ii, dx, dy를 [-1,1,0,0] [0,0,-1,1]로 선언해준다. 이는 앞으로 갈 곳의 상,하,좌,우 ny,nx를 계산하기 위해 필요하다.  (#D)

iii. 반복문을 돌며 (상,하,좌,우) ny = y + dy[i], nx = x + dx[i] 로 ny,nx값을 구해준다. 현재 y=0, x=0이기 때문에 ny = 0, nx = -1 이다. ny, nx가 0이상 5미만값이며 visited[ny][nx] 가 0일 경우만 취급한다. 0 ~ 5값을 확인하는 이유는 -1,6과 같은 좌표는 고려대상이 아니기 때문이다.

a) p[ny][nx]가 'O'라면 방문할 수 있는 곳이다. visited[ny][nx]= 1로 방문 표시를 해준다. distance[ny][nx]는 distance[y][x] + 1 로 현재 위치에 더하기 1값을 해준다. 그리고 queue에 [ny,nx]를 추가해준다. ny, nx가 내가 이동한 자리, 즉 내 현재 새로운 위치를 뜻한다. 이 새로운 위치에서 다시 i부터 실행해준다. (#B, #C)

b) p[ny][nx]가 P이지만, distance[y][x]가 1 이하인 경우에는 거리두기를 지키지 않은 것이기 때문에 return 0을 한다. #C

c) iii로 돌아가 반복한다. (#B)

d) iii의 반복이 끝나면 i를 queue가 빈배열이 될 때까지 반복된다.

d) i가 끝나면 2-1로 돌아가 다시 반복문을 돌며 위의 내용을 다시 반복한다. 모든 반복이 끝나면 거리두기를 잘 수행한 것이므로 1을 return해준다.

 

반복지옥이다

 

from collections import deque

def bfs(p):
  start = []
  for i in range(1):
    for j in range(5):
      if p[i][j] == 'P':
        start.append([i,j])

  for s in start:
    #print(' ')
    #print('start!', s, '-------------------------------')
    #print(' ')
    queue = deque([s])
    visited = [[0]* 5 for i in range(5)]
    distance = [[0]* 5 for i in range(5)]
    visited[s[0]][s[1]] = 1

    while queue:
      y, x = queue.popleft()
      #print('popleft', x, y)
      dx = [-1, 1, 0, 0]
      dy = [0, 0, -1, 1]

      for i in range(4):
        #print('dx[i]:', dx[i], ' x:', x, ' dy[i]:', dy[i], ' y:', y)
        print('')
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < 5 and 0 <= ny <5 and visited[ny][nx] == 0:
          if p[ny][nx] == 'O':
            queue.append([ny, nx])
            visited[ny][nx] = 1
            distance[ny][nx]= distance[y][x] + 1
          if p[ny][nx] == "P" and distance[y][x] <= 1:
            return 0
          #print('inside for - visited', visited)
          #print('inside for - distance', distance)
      #print('visited', visited)
      #print('queue', queue)
      #print('- - - - - - - - - - - - - - - - -')
  return 1
    
def solution(places):
  answer = []

  for i in places:
    answer.append(bfs(i))
  return answer 

print(solution([["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"]]))

# ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]



# start! [0, 0] -------------------------------
 
# popleft 0 0

# dx[i]: -1  x: 0  dy[i]: 0  y: 0 dx[i] 가 0보다 작기때문에 pass
# dx[i]: 1  x: 0  dy[i]: 0  y: 0

# inside for - visited [[1, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 0  dy[i]: -1  y: 0
# dx[i]: 0  x: 0  dy[i]: 1  y: 0

# inside for - visited [[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[0, 1], [1, 0]])
# - - - - - - - - - - - - - - - - -
 
# popleft 1 0

# dx[i]: -1  x: 1  dy[i]: 0  y: 0
# dx[i]: 1  x: 1  dy[i]: 0  y: 0

# inside for - visited [[1, 1, 1, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 1  dy[i]: -1  y: 0
# dx[i]: 0  x: 1  dy[i]: 1  y: 0

# inside for - visited [[1, 1, 1, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 1, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[1, 0], [0, 2]])
# - - - - - - - - - - - - - - - - -
 
# popleft 0 1

# dx[i]: -1  x: 0  dy[i]: 0  y: 1
# dx[i]: 1  x: 0  dy[i]: 0  y: 1

# inside for - visited [[1, 1, 1, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 0  dy[i]: -1  y: 1
# dx[i]: 0  x: 0  dy[i]: 1  y: 1

# inside for - visited [[1, 1, 1, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 0, 0], [1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 1, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[0, 2], [2, 0]])
# - - - - - - - - - - - - - - - - -
 
# popleft 2 0

# dx[i]: -1  x: 2  dy[i]: 0  y: 0


# dx[i]: 1  x: 2  dy[i]: 0  y: 0

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 2  dy[i]: -1  y: 0
# dx[i]: 0  x: 2  dy[i]: 1  y: 0

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[2, 0], [0, 3]])
# - - - - - - - - - - - - - - - - -
 
# popleft 0 2

# dx[i]: -1  x: 0  dy[i]: 0  y: 2
# dx[i]: 1  x: 0  dy[i]: 0  y: 2

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 0  dy[i]: -1  y: 2


# dx[i]: 0  x: 0  dy[i]: 1  y: 2

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [3, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[0, 3], [3, 0]])
# - - - - - - - - - - - - - - - - -
 
# popleft 3 0

# dx[i]: -1  x: 3  dy[i]: 0  y: 0
# dx[i]: 1  x: 3  dy[i]: 0  y: 0

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 0, 0], [2, 0, 0, 0, 0], [3, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 3  dy[i]: -1  y: 0
# dx[i]: 0  x: 3  dy[i]: 1  y: 0

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[3, 0], [1, 3]])
# - - - - - - - - - - - - - - - - -
 
# popleft 0 3

# dx[i]: -1  x: 0  dy[i]: 0  y: 3
# dx[i]: 1  x: 0  dy[i]: 0  y: 3

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 0  dy[i]: -1  y: 3
# dx[i]: 0  x: 0  dy[i]: 1  y: 3

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[1, 3], [3, 1]])
# - - - - - - - - - - - - - - - - -
 
# popleft 3 1

# dx[i]: -1  x: 3  dy[i]: 0  y: 1

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 1  x: 3  dy[i]: 0  y: 1

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 3  dy[i]: -1  y: 1
# dx[i]: 0  x: 3  dy[i]: 1  y: 1

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[3, 1]])
# - - - - - - - - - - - - - - - - -
 
# popleft 1 3

# dx[i]: -1  x: 1  dy[i]: 0  y: 3
# dx[i]: 1  x: 1  dy[i]: 0  y: 3

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 1  dy[i]: -1  y: 3

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 1  dy[i]: 1  y: 3

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 5, 0, 0, 0]]

# visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 0]]
# queue deque([[4, 1]])
# - - - - - - - - - - - - - - - - -
 
# popleft 1 4

# dx[i]: -1  x: 1  dy[i]: 0  y: 4

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 5, 0, 0, 0]]

# dx[i]: 1  x: 1  dy[i]: 0  y: 4

# inside for - visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 0]]
# inside for - distance [[0, 1, 2, 3, 0], [1, 0, 0, 4, 0], [2, 0, 0, 0, 0], [3, 4, 0, 0, 0], [0, 5, 0, 0, 0]]

# dx[i]: 0  x: 1  dy[i]: -1  y: 4
# dx[i]: 0  x: 1  dy[i]: 1  y: 4


# visited [[1, 1, 1, 1, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 0]]
# queue deque([])
# - - - - - - - - - - - - - - - - -
 
 
# start! [0, 4] -------------------------------
 
# popleft 4 0

# dx[i]: -1  x: 4  dy[i]: 0  y: 0

# inside for - visited [[0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 1  x: 4  dy[i]: 0  y: 0
# dx[i]: 0  x: 4  dy[i]: -1  y: 0
# dx[i]: 0  x: 4  dy[i]: 1  y: 0

# inside for - visited [[0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[0, 3]])
# - - - - - - - - - - - - - - - - -
 
# popleft 3 0

# dx[i]: -1  x: 3  dy[i]: 0  y: 0

# inside for - visited [[0, 0, 1, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 0, 2, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 1  x: 3  dy[i]: 0  y: 0
# dx[i]: 0  x: 3  dy[i]: -1  y: 0
# dx[i]: 0  x: 3  dy[i]: 1  y: 0

# inside for - visited [[0, 0, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 0, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[0, 0, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[0, 2], [1, 3]])
# - - - - - - - - - - - - - - - - -
 
# popleft 2 0

# dx[i]: -1  x: 2  dy[i]: 0  y: 0

# inside for - visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 3, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 1  x: 2  dy[i]: 0  y: 0
# dx[i]: 0  x: 2  dy[i]: -1  y: 0
# dx[i]: 0  x: 2  dy[i]: 1  y: 0

# inside for - visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 3, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[1, 3], [0, 1]])
# - - - - - - - - - - - - - - - - -
 
# popleft 3 1

# dx[i]: -1  x: 3  dy[i]: 0  y: 1

# inside for - visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 3, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 1  x: 3  dy[i]: 0  y: 1

# inside for - visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 3, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 0  x: 3  dy[i]: -1  y: 1
# dx[i]: 0  x: 3  dy[i]: 1  y: 1

# inside for - visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 3, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([[0, 1]])
# - - - - - - - - - - - - - - - - -
 
# popleft 1 0

# dx[i]: -1  x: 1  dy[i]: 0  y: 0

# inside for - visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 3, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# dx[i]: 1  x: 1  dy[i]: 0  y: 0
# dx[i]: 0  x: 1  dy[i]: -1  y: 0
# dx[i]: 0  x: 1  dy[i]: 1  y: 0

# inside for - visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# inside for - distance [[0, 3, 2, 1, 0], [0, 0, 0, 2, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

# visited [[0, 1, 1, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
# queue deque([])
# - - - - - - - - - - - - - - - - -
 
# [1]