row, column = [int(s) for s in input().rstrip().split()] start = [int(s)-1 for s in input().rstrip().split()] goal = [int(s)-1 for s in input().rstrip().split()] maze = [input().rstrip() for _ in range(row)] queue = [start] check = [[0 for _ in range(column)] for _ in range(row)] # 0: not checked, 1: checked route = [[0 for _ in range(column)] for _ in range(row)] # BFS while queue: # pop x, y = queue.pop(0) for i, j in [[x-1, y], [x, y-1], [x, y+1], [x+1, y]]: if maze[i][j] == '#' or check[i][j] == 1: continue route[i][j] = route[x][y] + 1 # push queue.append([i, j]) check[i][j] = 1 gx, gy = goal print(route[gx][gy])
Task問題 | C - 幅優先探索 |
---|---|
User nameユーザ名 | kirikirijin |
Created time投稿日時 | |
Language言語 | Python3 (3.4.3) |
Status状態 | AC |
Score得点 | 100 |
Source lengthソースコード長 | 714 Byte |
File nameファイル名 | |
Exec time実行時間 | 24 ms |
Memory usageメモリ使用量 | 3064 KB |
Set name | Score得点 / Max score | Cases |
---|---|---|
Sample | - | subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt |
All | 100 / 100 | 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 usageメモリ使用量 |
---|---|---|---|
subtask0_sample01.txt | AC | 18 ms | 3064 KB |
subtask0_sample02.txt | AC | 18 ms | 3064 KB |
subtask0_sample03.txt | AC | 23 ms | 3064 KB |
subtask1_01.txt | AC | 21 ms | 3064 KB |
subtask1_02.txt | AC | 21 ms | 3064 KB |
subtask1_03.txt | AC | 21 ms | 3064 KB |
subtask1_04.txt | AC | 23 ms | 3064 KB |
subtask1_05.txt | AC | 24 ms | 3064 KB |
subtask1_06.txt | AC | 22 ms | 3064 KB |
subtask1_07.txt | AC | 17 ms | 3064 KB |
subtask1_08.txt | AC | 18 ms | 3064 KB |
subtask1_09.txt | AC | 21 ms | 3064 KB |
subtask1_10.txt | AC | 19 ms | 3064 KB |
subtask1_11.txt | AC | 23 ms | 3064 KB |
subtask1_12.txt | AC | 23 ms | 3064 KB |
subtask1_13.txt | AC | 21 ms | 3064 KB |
subtask1_14.txt | AC | 18 ms | 3064 KB |
subtask1_15.txt | AC | 22 ms | 3064 KB |
subtask1_16.txt | AC | 21 ms | 3064 KB |
subtask1_17.txt | AC | 23 ms | 3064 KB |
subtask1_18.txt | AC | 22 ms | 3064 KB |
subtask1_19.txt | AC | 21 ms | 3064 KB |
subtask1_20.txt | AC | 21 ms | 3064 KB |
subtask1_21.txt | AC | 21 ms | 3064 KB |
subtask1_22.txt | AC | 21 ms | 3064 KB |