Submission #1988268


Source Code Expand

r, c = [int(x) for x in input().split()]
sy, sx = [int(x) for x in input().split()]
gy, gx = [int(x) for x in input().split()]

map = []    # map読込用
g = {}      # 隣接リスト
for _ in range(r):
    map.append(list(input()))
for i, l in enumerate(map):
    #    print(l)
    for j, f in enumerate(l):
        if f == "#":
            g[i * c + j] = None
        else:
            lt = []
            if map[i - 1][j] == ".":
                lt.append((i - 1) * c + j)
            if map[i + 1][j] == ".":
                lt.append((i + 1) * c + j)
            if map[i][j - 1] == ".":
                lt.append(i * c + j - 1)
            if map[i][j + 1] == ".":
                lt.append(i * c + j + 1)
            g[i * c + j] = lt
# print(g)

start = (sy - 1) * c + sx - 1
goal = (gy - 1) * c + gx - 1
frontier = []
frontier.append(start)
visited = {}
visited[start] = True
route = {}
route[start] = [start]

while len(frontier) > 0:
    current = frontier.pop(0)
#    print("Visiting {}".format(current))
    if current == goal:
#        print(route[goal])
        print(len(route[goal]) - 1)
    for next in g[current]:
        if next not in visited:
            frontier.append(next)
            visited[next] = True
            route[next] = route[current] + [next]

Submission Info

Submission Time
Task C - 幅優先探索
User eiji0313
Language Python (3.4.3)
Score 100
Code Size 1329 Byte
Status AC
Exec Time 35 ms
Memory 9332 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 18 ms 3064 KB
subtask0_sample02.txt AC 18 ms 3064 KB
subtask0_sample03.txt AC 28 ms 4972 KB
subtask1_01.txt AC 32 ms 8948 KB
subtask1_02.txt AC 33 ms 8948 KB
subtask1_03.txt AC 23 ms 4084 KB
subtask1_04.txt AC 28 ms 4972 KB
subtask1_05.txt AC 28 ms 4972 KB
subtask1_06.txt AC 29 ms 6388 KB
subtask1_07.txt AC 17 ms 3064 KB
subtask1_08.txt AC 19 ms 3316 KB
subtask1_09.txt AC 24 ms 4336 KB
subtask1_10.txt AC 21 ms 3572 KB
subtask1_11.txt AC 27 ms 4844 KB
subtask1_12.txt AC 26 ms 4464 KB
subtask1_13.txt AC 24 ms 3956 KB
subtask1_14.txt AC 18 ms 3316 KB
subtask1_15.txt AC 24 ms 4596 KB
subtask1_16.txt AC 24 ms 4212 KB
subtask1_17.txt AC 25 ms 4596 KB
subtask1_18.txt AC 25 ms 4464 KB
subtask1_19.txt AC 26 ms 6004 KB
subtask1_20.txt AC 30 ms 8052 KB
subtask1_21.txt AC 35 ms 9332 KB
subtask1_22.txt AC 31 ms 8180 KB