This question already has an answer here:
- Textual maze solver 4 answers
Your job is to find the shortest path from point A to point B. The path must be represented as a list of moves (
U for up,
D for down,
L for left and
R for right). You can only move in 4 directions, no diagonals allowed.
You're given a map, filled with zeroes and ones. This map must be read from the STDIN if it is possible in your language. Otherwise, you're given the freedom to pass it as a function argument. The input also contains the starting and ending coordinates. Here's an example input: (no comments will be sent to your program)
8 4 # This stands for map with a width of 8 and height of 4 2 1 # Point A (1,2) 7 3 # Point B (7,3) 00000000 # And the map 00010000 00010000 00000000
Coordinates are zero-indexed, so they would be placed like this:
00000000 00A10000 00010000 0000000B
Output from this should be
DDRRRRR. This output value should be printed to STDOUT or returned from the function, respectively. The map can be of size between 1x1 to 2^31 x 2^31. If two or more paths are equal, you're allowed to print any one of them. If the points are the same or there's no path between the points, the program can crash, print nothing, throw an error.. Whatever really.
Shortest code wins, but do show some love to smart answers.
5 7 0 0 4 6 00000 11010 00000 11110 00000 01111 00000
RRDDRRDDLLLLDDRRRR or RRRRDDDDLLLLDDRRRR
5 2 1 1 0 4 00100 00100
6 6 0 0 5 0 000000 110110 010000 011111 000000 000000