Submission #3040571


Source Code Expand

R, C = list(map(int, input().split()))
sy, sx = list(map(int, input().split()))
gy, gx = list(map(int, input().split()))
c = [input() for _ in range(R)]

moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] 

def bfs():
    visited = []
    dist = [[1 for _ in range(C)] for _ in range(R)]
    routes = [(sx-1, sy-1)]
    visited.append((sx-1, sy-1))

    hop_count = 0 
    while len(routes) > 0:
        x, y = routes.pop(0)
        for move in moves:
            cx = x + move[0]
            cy = y + move[1]
            if cx < 0 or cy < 0 or cx >= C or cy >= R or c[cy][cx] == '#' or (cx, cy) in visited:
                continue
            if cx == gx-1 and cy == gy-1: 
                return dist[y][x]
            visited.append((cx, cy))
            routes.append((cx, cy))
            dist[cy][cx] = dist[y][x] + 1 

print(bfs())

Submission Info

Submission Time
Task C - 幅優先探索
User koujiokada
Language Python (3.4.3)
Score 100
Code Size 858 Byte
Status AC
Exec Time 276 ms
Memory 3188 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 17 ms 3064 KB
subtask0_sample02.txt AC 17 ms 3064 KB
subtask0_sample03.txt AC 276 ms 3188 KB
subtask1_01.txt AC 54 ms 3064 KB
subtask1_02.txt AC 55 ms 3064 KB
subtask1_03.txt AC 44 ms 3064 KB
subtask1_04.txt AC 276 ms 3188 KB
subtask1_05.txt AC 73 ms 3064 KB
subtask1_06.txt AC 137 ms 3188 KB
subtask1_07.txt AC 17 ms 3064 KB
subtask1_08.txt AC 18 ms 3064 KB
subtask1_09.txt AC 66 ms 3064 KB
subtask1_10.txt AC 21 ms 3064 KB
subtask1_11.txt AC 271 ms 3188 KB
subtask1_12.txt AC 130 ms 3064 KB
subtask1_13.txt AC 67 ms 3064 KB
subtask1_14.txt AC 17 ms 3064 KB
subtask1_15.txt AC 80 ms 3064 KB
subtask1_16.txt AC 80 ms 3064 KB
subtask1_17.txt AC 155 ms 3188 KB
subtask1_18.txt AC 108 ms 3064 KB
subtask1_19.txt AC 53 ms 3064 KB
subtask1_20.txt AC 61 ms 3064 KB
subtask1_21.txt AC 92 ms 3188 KB
subtask1_22.txt AC 59 ms 3064 KB