Submission #691993

Source Code Expand

r,c = map(int,raw_input().split(' '))
sy,sx = map(int,raw_input().split(' '))
gy,gx = map(int,raw_input().split(' '))
maze = [list(raw_input()) for i in xrange(r)]
sy-=1
sx-=1
gy-=1
gx-=1
import Queue
q = Queue.Queue()
around = lambda p:[[p[0]-1,p[1]],[p[0],p[1]+1],[p[0]+1,p[1]],[p[0],p[1]-1]]
movable = lambda p: False if (not 0<=p[0]<r) or (not 0<=p[1]<c) else True if maze[p[0]][p[1]] == '.' else False
isGoal = lambda p: True if p[0]==gy and p[1]==gx else False
dp = [[None for i in xrange(c)] for j in xrange(r)]
q.put([sy,sx])
dp[sy][sx] = 0
while not q.empty():
	p = q.get()
	if isGoal(p): break
	for a in around(p):
		if movable(a) and (dp[a[0]][a[1]] == None or dp[a[0]][a[1]] > dp[p[0]][p[1]]+1):
			dp[a[0]][a[1]] = dp[p[0]][p[1]]+1
			q.put(a)
print dp[gy][gx]

Submission Info

Submission Time
Task A - 幅優先探索
User yasuke
Language Python (2.7.6)
Score 100
Code Size 796 Byte
Status AC
Exec Time 694 ms
Memory 7140 KiB

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 694 ms 7140 KiB
subtask0_sample02.txt AC 30 ms 3052 KiB
subtask0_sample03.txt AC 66 ms 3052 KiB
subtask1_01.txt AC 47 ms 3052 KiB
subtask1_02.txt AC 47 ms 3052 KiB
subtask1_03.txt AC 45 ms 3052 KiB
subtask1_04.txt AC 67 ms 3052 KiB
subtask1_05.txt AC 48 ms 3052 KiB
subtask1_06.txt AC 56 ms 3052 KiB
subtask1_07.txt AC 30 ms 3052 KiB
subtask1_08.txt AC 32 ms 3052 KiB
subtask1_09.txt AC 48 ms 3052 KiB
subtask1_10.txt AC 36 ms 3052 KiB
subtask1_11.txt AC 66 ms 3052 KiB
subtask1_12.txt AC 55 ms 3052 KiB
subtask1_13.txt AC 50 ms 3052 KiB
subtask1_14.txt AC 31 ms 3052 KiB
subtask1_15.txt AC 51 ms 3052 KiB
subtask1_16.txt AC 52 ms 3052 KiB
subtask1_17.txt AC 59 ms 3052 KiB
subtask1_18.txt AC 55 ms 3052 KiB
subtask1_19.txt AC 49 ms 3052 KiB
subtask1_20.txt AC 49 ms 3052 KiB
subtask1_21.txt AC 52 ms 3052 KiB
subtask1_22.txt AC 52 ms 3052 KiB