How to solve a given 2D maze-CodePudding

I am kind of a beginner in Python so I still have lots to learn. This was a problem I encountered during competitive programming and even after I still can't figure out a suitable way to solve it. Could anyone guide me through on how to solve these types of questions?

Mary Jane has run out of milk! She asked Spidey to get some, but someone has stolen all the milk from all the stores in the area, so you need to find out of Spider-Man can get to the last milk in the city in time for dinner.

Input Format

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with 3 integers, r, c and Ss. Each of the next r lines will consist of c characters, denoting the layout of the city that Spidey will have to traverse to get the milk, with the following characters having the following meetings.

S – denotes the location of Spider-Man in the city.

# - denotes the location of a building in the city, it takes 3 seconds to traverse one of these.

. – denotes an open street, it takes 1 second to traverse one of these.

Y, U, L, R, E – denotes the location of minor villains (Mysterio, Vulture, Lizard, Rhino, Electro) in the city, if you travel through one of these it takes 5 seconds to defeat them before you can move on.

D, V, C – denotes the location of major villains (Doctor Octopus, Venom, Carnage) in the city, and it takes 8 seconds to defeat them before you can move on.

M – denotes the location of the milk in the city, this is the end point of the maze.

Note: There is not always a guaranteed path to the milk. There may not be any milk in New York in which case it’s an automatic failure. Spidey can only move up, down, left, and right, no diagonals.

Constraints

None.

Output Format

If Spider-Man gets the milk in less than s seconds, output "Everything's peachy, Spidey escaped in ", followed by how many steps it took Spider-Man to escape, followed by " seconds.". Otherwise, output "Spidey's having marital problems.".

Sample Input 0

2
5 6 9
S..#..
##..R#
.#.#.#
#M..#.
#..#.#
7 7 5
#..#S.#
#Y..L.#
..#.U.V
O.#..#M
..#..DY
#......
.#.#.C.

Sample Output 0

Everything's peachy, Spidey escaped in 6 seconds.
Spidey's having marital problems.

CodePudding user response：

Hmmm, villain / building obstacles pose an interesting twist.

Without them, a simple Flood Fill would let you at least answer the Boolean question "is there milk?"

With them, this is starting to look a lot like a weighted (undirected) graph.

So a map such as this example

AB
CD

would be a four-node graph with edges

A - B
A - C
B - D
C - D

with unit weights, and then networkx would make short work of such a graph, directly giving the path for Spidey to follow.

Each obstacle will increase the weights of two, three, or four edges.

It's not explicitly spelled out, but apparently there is unit cost to enter the Milk location.

Gotham is a big town.

A disadvantage of the approach above is it ignores the threshold parameter s. That is, it will find a path if one exists, even if the path is useless since it exceeds the threshold. That can take some seconds of CPU time.

Put another way, for very large graphs, we would like to terminate early if we can prove that no "short enough" path exists.

Consider doing flood fill, where you mark each location with the minimum cost to get there. When all such costs exceed s, bail out early to report failure. This will help with scaling up to very large maps.

CodePudding user response：

This is a standard shortest path problem on a grid graph with double directed edges. The nodes are the grid elements. The "in" edges for each vertex get the cost of the respective grid square type at the head of the edge. Then use a standard shortest path algorithm like Dijkstra to find all the shortest distances from Spidy's location to each of the milk locations. Finally, take the smallest of those.

You don't actually need to construct a graph. Just use the string representation and implement Dijkstra's to infer the edges and their costs on the fly.