That's my first problem here. I just pressed Random button and got it. Graveyard problem. After reading I felt that it was all about Bellman-Ford algorithm. It just solves all the needed problems. So I wrote a straightforward solution but I got Time Exceeded Error on the first test. Now I'm not clearly sure what's the problem.
As I said it's my first task here therefore I should ask if it is possible that something is wrong with reading input? On my PC I run program with:
`cat input | python graveyard.py`
Where input
contains the example presented on the problem page.
Or there is a secret way to optimize the solution?
So here is my code, I tried to comment it well.
Thanks!
# If dist[v] == UNAWARED than there is no way to v
UNAWARED = 1000000000000
# Cost to travel to neighbor cell
FREE_COST = 1
# initial position
ENTRANCE = (0, 0)
deltas = [[0, 1],
[0, -1],
[1, 0],
[-1, 0]]
def check_delta(shape, pos, delta):
"""
If it's possible to get from pos to pos+delta then
return pos+delta, otherwise return None
"""
x_new = pos[0] + delta[0]
y_new = pos[1] + delta[1]
if (x_new < 0) or (x_new >= shape[0]):
return None
if (y_new < 0) or (y_new >= shape[1]):
return None
return x_new, y_new
def pos_to_v(shape, pos):
"""
Translates map coordinates to graph vertex number
shape --- size of map (h, w)
"""
return pos[0]*shape[1] + pos[1]
def build_edges():
"""
Create edges graph representation
Firstly it creates graph with all the neighbors connected
Then when reading gravestone and holes it removes/add connections
edges[v] --- all edges which are incident with v
edges[v][i][0] --- destination vertex
edges[v][i][1] --- weight to travel from v to destination(1 for grass, t for hole)
shape --- shape of graveyard
if shape == (0, 0) (end of test cases)
return None
otherwise
return edges, shape
"""
shape = [int(x) for x in raw_input().split(' ')]
if (shape[0] == 0) and (shape[1] == 0):
return None
v_num = (shape[0]*shape[1])
edges = [0]*v_num
# Build graph with all neighbors connected
for v in range(v_num):
i = int(v / shape[1])
j = int(v % shape[1])
subedges = list()
for d in deltas:
new_pos = check_delta(shape, (i,j), d)
if new_pos:
new_v = pos_to_v(shape, new_pos)
subedges.append((new_v, FREE_COST))
edges[v] = subedges
gravestones = int(raw_input())
# All paths from/to gravestone tile are being removed
for i in range(gravestones):
grave_pos = [int(x) for x in raw_input().split(' ')]
v = pos_to_v(shape, grave_pos)
# Iteratively remove edges from v and
# edges from destination vertex to v
while len(edges[v]) > 0:
e = edges[v].pop(0)
edges[e[0]].remove((v, FREE_COST))
holes = int(raw_input())
# All paths from hole tile are being removed
# Path from hole to destination is being added
for i in range(holes):
hole_info = [int(x) for x in raw_input().split(' ')]
hole_pos = hole_info[0:2]
hole_dest = hole_info[2:4]
hole_time = hole_info[4]
v = pos_to_v(shape, hole_pos)
d = pos_to_v(shape, hole_dest)
edges[v] = [[d, hole_time]]
return edges, shape
def ford_bellman(edges, dist):
"""
Just a Bellman-Ford algorithm
If negative cycle is found then return None otherwise
return an array of distances
"""
l = len(edges)
for relax in range(l):
for v in range(l):
for i in range(len(edges[v])):
new_dist = dist[v] + edges[v][i][1]
if dist[edges[v][i][0]] > new_dist:
dist[edges[v][i][0]] = new_dist
for v in range(l):
for i in range(len(edges[v])):
if dist[v] + edges[v][i][1] < dist[edges[v][i][0]]:
return None
return dist
if __name__ == "__main__":
graph = build_edges()
while graph:
edges = graph[0]
shape = graph[1]
EXIT = (shape[0]-1, shape[1]-1)
# Initially fill all distances with infinity
# Only starting position has distance 0
dist = [UNAWARED]*(shape[0]*shape[1])
dist[pos_to_v(shape, ENTRANCE)] = 0
# Find shortest paths
dist = ford_bellman(edges, dist)
# Print result
if not dist:
print("Never")
elif dist[pos_to_v(shape, EXIT)] == UNAWARED:
print("Impossible")
else:
print(str(dist[pos_to_v(shape, EXIT)]))
graph = build_edges()