Submission #35553

#	Time	Username	Problem	Language	Result	Execution time	Memory
35553		leejseo	Portals (BOI14_portals)	Cpython 2	20 / 100	448 ms	21 KiB

portals

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))
'''

def isWall(row, col):
    if not( 0 <= row < R  and 0 <= col < C ): return True
    return M[row][col] == "#"

adj = [ [False]*C for i in range(R) ]

for row in range(R):
    for col in range(C):
        if M[row][col] != "#":
            for i in range(4):
                r_ = row + delta_row[i]
                c_ = col + delta_col[i]
                adj[row][col] = adj[row][col] or isWall(r_, c_)

for row in range(R):
    left = None
    for col in range(C):
        if M[row][col] != "#":
            if left == None: left = col
            elif adj[row][col]:
                adj_list[row][col].append((row, left))
        else: left = None
    right = None
    for col in range(C-1, -1, -1):
        if M[row][col] != "#":
            if right == None: right = col
            elif adj[row][col]:
                adj_list[row][col].append((row, right))
        else: right = None

for col in range(C):
    up = None
    for row in range(R):
        if M[row][col] != "#":
            if up == None: up = row
            elif adj[row][col]:
                adj_list[row][col].append((up, col))
        else: up = None
    down = None
    for row in range(R-1, -1, -1):
        if M[row][col] != "#":
            if down == None: down = row
            elif adj[row][col]:
                adj_list[row][col].append((down, col))
        else: down = None

####### 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]

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30