This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
from collections import deque
from heapq import *
from sys import maxint
R, C = map(int, raw_input().split())
M = [None]*R
for i in xrange(R):
M[i] = list(raw_input())
####### FIND THE POSITION OF S, C #######
start = None
cake = None
for i in xrange(R):
for j in xrange(C):
if M[i][j] == "S":
start = (i, j)
continue
if M[i][j] == "C":
cake = (i, j)
def check(row, col):
return M[row][col] != "#" and BT[row][col] == None
####### BFS WITH BACKTRAKING #######
BT = [ [None] * C for i in xrange(R) ]
l, r, u, d = 0, 1, 2, 3
queue = deque([cake])
while queue:
row, col = queue.popleft()
if row < R-1:
if check(row+1, col):
BT[row+1][col] = u
queue.append((row+1, col))
if row > 0 :
if check(row-1, col):
BT[row-1][col] = d
queue.append((row-1, col))
if col < C-1 :
if check(row, col+1):
BT[row][col+1] = l
queue.append((row, col+1))
if col > 0 :
if check(row, col-1):
BT[row][col-1] = r
queue.append((row, col-1))
####### BUILD GRAPH FOR DIJKSTRA'S ALGORITHM #######
delta_col = [-1, 1, 0, 0]
delta_row = [0, 0, -1, 1]
adj_list = [ [ [] for col in xrange(C) ] for row in xrange(R) ]
def valid(row, col):
if not( 0 <= row < R and 0 <= col < C ): return False
return M[row][col] != "#"
for row in xrange(R):
for col in xrange(C):
if row > 0 :
if valid(row-1, col):
adj_list[row][col].append((row-1, col))
if row < R-1:
if valid(row+1, col):
adj_list[row][col].append((row+1, col))
if col > 0 :
if valid(row, col-1):
adj_list[row][col].append((row, col-1))
if col < C-1:
if valid(row, col+1):
adj_list[row][col].append((row, col+1))
####### ADD PORTALS #######
er, ec = cake
row, col = start
bf = None
to_shoot = [] # tuple of ((row, col), dir)
while row != er or col != ec :
i = BT[row][col]
if bf != None and i != bf:
to_shoot.append(((row, col), i))
bf = i
row += delta_row[i]
col += delta_col[i]
def set_portal(place, i):
row, col = place
r_ = row+ delta_row[i]
c_ = col+ delta_col[i]
while valid(r_, c_):
row = r_
col = c_
r_ = row+ delta_row[i]
c_ = col+ delta_col[i]
return row, col
for t in to_shoot:
place, i = t
sr, sc = place
row, col = set_portal(place, i)
adj_list[sr][sc].append((row, col))
####### DIJKSTRA'S ALGORITHM #######
dist = [ [maxint]*C for i in range(R) ]
sr, sc = start
dist[sr][sc] = 0
Q = []
heappush(Q, (0, start))
while Q:
weight, place = heappop(Q)
p_row, p_col = place
for v in adj_list[p_row][p_col]:
vr, vc = v
dist_v = weight + 1
if dist_v < dist[vr][vc]:
dist[vr][vc] = dist_v
heappush(Q, (dist_v, (vr, vc)))
cr, cc = cake
print dist[cr][cc]
# | 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... |