Submission #9458251


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

H,W = map(int,readline().split())
H += 2; W += 2
grid = '#' * W
for _ in range(H-2):
    grid += '#' + readline().rstrip().decode() + '#'
grid += '#' * W

def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '#':
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return max(x for x in dist if x < INF)

answer = max(bfs(v) for v in range(H*W) if grid[v] != '#')
print(answer)

Submission Info

Submission Time
Task D - Maze Master
User maspy
Language Python (3.4.3)
Score 400
Code Size 855 Byte
Status AC
Exec Time 183 ms
Memory 3316 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 16
Set Name Test Cases
Sample sample_01, sample_02
All hand_01, hand_02, hand_03, hand_04, hand_05, hand_06, hand_07, hand_08, hand_09, hand_10, sample_01, sample_02, small_01, small_02, small_03, small_04
Case Name Status Exec Time Memory
hand_01 AC 62 ms 3316 KB
hand_02 AC 27 ms 3316 KB
hand_03 AC 27 ms 3316 KB
hand_04 AC 46 ms 3316 KB
hand_05 AC 80 ms 3316 KB
hand_06 AC 77 ms 3316 KB
hand_07 AC 39 ms 3316 KB
hand_08 AC 183 ms 3316 KB
hand_09 AC 25 ms 3316 KB
hand_10 AC 28 ms 3316 KB
sample_01 AC 20 ms 3316 KB
sample_02 AC 21 ms 3316 KB
small_01 AC 20 ms 3316 KB
small_02 AC 21 ms 3316 KB
small_03 AC 64 ms 3316 KB
small_04 AC 21 ms 3316 KB