Submission #73589993

Source Code Expand

from collections import deque
n,m=map(int,input().split())
s=[input() for i in range(n)]
d=[[float('inf')]*m for i in range(n)]
d[0][0]=0
q=deque([(0,0)])
while q:
    i,j=q.popleft()
    for di,dj in [(0,1),(1,0),(0,-1),(-1,0)]:
        ni,nj=i+di,j+dj
        if 0<=ni<n and 0<=nj<m:
            if s[ni][nj]=="#" and d[ni][nj]>d[i][j]+1:
                d[ni][nj]=d[i][j]+1
                q.append((ni,nj))
            elif s[ni][nj]=='.' and d[ni][nj]>d[i][j]:
                d[ni][nj]=d[i][j]
                q.append((ni,nj))
print(d[-1][-1])

Submission Info

Submission Time
Task D - Escape from the Maze
User itokoi
Language Python (PyPy 3.11-v7.3.20)
Score 400
Code Size 567 Byte
Status AC
Exec Time 1039 ms
Memory 193540 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 10
AC × 62
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, sample06.txt, sample07.txt, sample08.txt, sample09.txt, sample10.txt
All sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, sample06.txt, sample07.txt, sample08.txt, sample09.txt, sample10.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in50.txt, in51.txt, in52.txt
Case Name Status Exec Time Memory
in01.txt AC 69 ms 93700 KiB
in02.txt AC 70 ms 93752 KiB
in03.txt AC 70 ms 93672 KiB
in04.txt AC 77 ms 102312 KiB
in05.txt AC 78 ms 103464 KiB
in06.txt AC 106 ms 110932 KiB
in07.txt AC 105 ms 111296 KiB
in08.txt AC 110 ms 111408 KiB
in09.txt AC 108 ms 111084 KiB
in10.txt AC 1039 ms 193540 KiB
in11.txt AC 411 ms 139400 KiB
in12.txt AC 496 ms 146324 KiB
in13.txt AC 121 ms 115728 KiB
in14.txt AC 130 ms 115824 KiB
in15.txt AC 76 ms 102092 KiB
in16.txt AC 78 ms 103196 KiB
in17.txt AC 110 ms 111316 KiB
in18.txt AC 1024 ms 189328 KiB
in19.txt AC 109 ms 111076 KiB
in20.txt AC 126 ms 115788 KiB
in21.txt AC 115 ms 110904 KiB
in22.txt AC 775 ms 168136 KiB
in23.txt AC 167 ms 118860 KiB
in24.txt AC 108 ms 111076 KiB
in25.txt AC 98 ms 110136 KiB
in26.txt AC 75 ms 101584 KiB
in27.txt AC 76 ms 102172 KiB
in28.txt AC 109 ms 111116 KiB
in29.txt AC 88 ms 108836 KiB
in30.txt AC 70 ms 93892 KiB
in31.txt AC 128 ms 115988 KiB
in32.txt AC 123 ms 115780 KiB
in33.txt AC 76 ms 102292 KiB
in34.txt AC 114 ms 111196 KiB
in35.txt AC 124 ms 115760 KiB
in36.txt AC 975 ms 185492 KiB
in37.txt AC 158 ms 118760 KiB
in38.txt AC 75 ms 102084 KiB
in39.txt AC 81 ms 105444 KiB
in40.txt AC 124 ms 115784 KiB
in41.txt AC 745 ms 171228 KiB
in42.txt AC 117 ms 110496 KiB
in43.txt AC 974 ms 185644 KiB
in44.txt AC 286 ms 128820 KiB
in45.txt AC 723 ms 170900 KiB
in46.txt AC 708 ms 163012 KiB
in47.txt AC 79 ms 104040 KiB
in48.txt AC 79 ms 103944 KiB
in49.txt AC 129 ms 115852 KiB
in50.txt AC 131 ms 115784 KiB
in51.txt AC 124 ms 115852 KiB
in52.txt AC 123 ms 115776 KiB
sample01.txt AC 70 ms 93812 KiB
sample02.txt AC 70 ms 93764 KiB
sample03.txt AC 70 ms 93812 KiB
sample04.txt AC 70 ms 94008 KiB
sample05.txt AC 70 ms 93736 KiB
sample06.txt AC 69 ms 93804 KiB
sample07.txt AC 69 ms 93968 KiB
sample08.txt AC 70 ms 93844 KiB
sample09.txt AC 70 ms 94356 KiB
sample10.txt AC 70 ms 94068 KiB