Submission #691656


Source Code Expand

xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def euclid_dis(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0

#n=int(raw_input())
r,c=map(int,raw_input().split())
sy,sx=map(int,raw_input().split())
gy,gx=map(int,raw_input().split())
q=set([(sy-1,sx-1)])
#l=map(int,raw_input().split())
l=[]
for i in range(r):
    l.append(list(raw_input()))
l[sy-1][sx-1]=0
while len(q):
    ny,nx=q.pop()
    for y,x in xy:
        iy,ix=ny+y,nx+x
        if 0<iy<r-1 and 0<ix<c-1:
            if l[iy][ix]=='.':
                l[iy][ix]=l[ny][nx]+1
                q.add((iy,ix))
            elif type(l[iy][ix])==int:
                #l[iy][ix]=min(l[iy][ix],l[ny][nx]+1)
                if l[iy][ix]>l[ny][nx]+1:
                    l[iy][ix]=l[ny][nx]+1
                    q.add((iy,ix))
print l[gy-1][gx-1]

Submission Info

Submission Time
Task A - 幅優先探索
User nyon
Language Python (2.7.6)
Score 100
Code Size 1028 Byte
Status AC
Exec Time 317 ms
Memory 3080 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 317 ms 3080 KB
subtask0_sample02.txt AC 26 ms 2696 KB
subtask0_sample03.txt AC 44 ms 2696 KB
subtask1_01.txt AC 33 ms 2696 KB
subtask1_02.txt AC 37 ms 2764 KB
subtask1_03.txt AC 33 ms 2696 KB
subtask1_04.txt AC 43 ms 2764 KB
subtask1_05.txt AC 43 ms 2696 KB
subtask1_06.txt AC 50 ms 2696 KB
subtask1_07.txt AC 26 ms 2696 KB
subtask1_08.txt AC 27 ms 2696 KB
subtask1_09.txt AC 34 ms 2696 KB
subtask1_10.txt AC 28 ms 2696 KB
subtask1_11.txt AC 43 ms 2764 KB
subtask1_12.txt AC 47 ms 2820 KB
subtask1_13.txt AC 35 ms 2696 KB
subtask1_14.txt AC 28 ms 2696 KB
subtask1_15.txt AC 37 ms 2696 KB
subtask1_16.txt AC 38 ms 2696 KB
subtask1_17.txt AC 43 ms 2696 KB
subtask1_18.txt AC 39 ms 2696 KB
subtask1_19.txt AC 34 ms 2696 KB
subtask1_20.txt AC 39 ms 2764 KB
subtask1_21.txt AC 40 ms 2820 KB
subtask1_22.txt AC 33 ms 2764 KB