This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#-*- coding: utf-8 -*-
maxint = int(2E9)
from collections import deque
N, M = map(int, raw_input().split())
B = [None]*M
P = [None]*M
for i in range(M):
B[i], P[i] = map(int, raw_input().split())
def BFS(B, P, N):
visited = [ [maxint]*N for i in range(N) ]
initial_pos = [[] for i in range(N) ]
for i in range(len(B)):
initial_pos[B[i]].append(P[i])
#### NOTE : visited[i][j] = pos : i, power : j ####
spos, spower = B[0], P[0]
gpos, gpower = B[1], P[1]
visited[spos][spower] = 0
Q = deque([(spos, spower)])
while Q:
#print Q
pos, power = Q.popleft()
val = visited[pos][power]
if pos - power > 0 :
if visited[pos-power][power] == maxint:
Q.append((pos-power, power))
visited[pos-power][power] = val + 1
if initial_pos[pos-power]:
for n_power in initial_pos[pos-power]:
if n_power == power : continue
if visited[pos-power][n_power] == maxint:
visited[pos-power][n_power] = val + 1
Q.append((pos-power, n_power))
if pos + power < N :
if visited[pos+power][power] == maxint:
Q.append((pos+power, power))
visited[pos+power][power] = val + 1
if initial_pos[pos+power]:
for n_power in initial_pos[pos+power]:
if n_power == power : continue
if visited[pos+power][n_power] == maxint:
visited[pos+power][n_power] = val+1
Q.append((pos+power, n_power))
#for i in visited: print i
ans = min(visited[gpos])
if ans == maxint: return -1
return ans
print BFS(B, P, N)
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |