Submission #1985881


Source Code Expand

import queue as queue
r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
a = [list(input()) for z in range(r)]
distance = [[-1 for j in range(c)] for i in range(r)]

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

ans = 0

def bfs():
  start = {
    "x": sx-1, 
    "y": sy-1
  }
  distance[sy-1][sx-1] = 0

  q = queue.Queue()
  q.put(start)

  while q.empty() == False:
    p = q.get()
    for i in range(4):
      nx = p["x"] + dx[i]
      ny = p["y"] + dy[i]
      if 0 <= ny <= r - 1 and 0 <= nx <= c - 1:
        if a[ny][nx] == "." and distance[ny][nx] == -1:
          distance[ny][nx] = distance[p["y"]][p["x"]] + 1
          if ny == gy-1 and nx == gx-1:
            ans = distance[ny][nx]
          else:
            q.put({"x": nx, "y": ny})

  print(ans)

if __name__ == "__main__":

  bfs()

    


    
  

Submission Info

Submission Time
Task C - 幅優先探索
User ProKoji
Language Python (3.4.3)
Score 100
Code Size 910 Byte
Status AC
Exec Time 49 ms
Memory 3952 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 25
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 35 ms 3952 KB
subtask0_sample02.txt AC 26 ms 3952 KB
subtask0_sample03.txt AC 47 ms 3952 KB
subtask1_01.txt AC 37 ms 3952 KB
subtask1_02.txt AC 37 ms 3952 KB
subtask1_03.txt AC 38 ms 3952 KB
subtask1_04.txt AC 49 ms 3952 KB
subtask1_05.txt AC 47 ms 3952 KB
subtask1_06.txt AC 43 ms 3952 KB
subtask1_07.txt AC 26 ms 3952 KB
subtask1_08.txt AC 28 ms 3952 KB
subtask1_09.txt AC 39 ms 3952 KB
subtask1_10.txt AC 30 ms 3952 KB
subtask1_11.txt AC 47 ms 3952 KB
subtask1_12.txt AC 46 ms 3952 KB
subtask1_13.txt AC 38 ms 3952 KB
subtask1_14.txt AC 27 ms 3952 KB
subtask1_15.txt AC 39 ms 3952 KB
subtask1_16.txt AC 39 ms 3952 KB
subtask1_17.txt AC 43 ms 3952 KB
subtask1_18.txt AC 41 ms 3952 KB
subtask1_19.txt AC 38 ms 3952 KB
subtask1_20.txt AC 37 ms 3952 KB
subtask1_21.txt AC 40 ms 3952 KB
subtask1_22.txt AC 38 ms 3952 KB