0
\$\begingroup\$

This question already has an answer here:

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.

Test cases:

Input:

5 7
0 0
4 6
00000
11010
00000
11110
00000
01111
00000

Output:

   RRDDRRDDLLLLDDRRRR
or RRRRDDDDLLLLDDRRRR

Input:

5 2
1 1
0 4
00100
00100

Output: Anything.

Input:

6 6
0 0
5 0
000000
110110
010000
011111
000000
000000

Output: RRRRR

\$\endgroup\$

marked as duplicate by Peter Taylor, Martin Ender, ProgramFOX, John Dvorak, squeamish ossifrage May 29 '14 at 12:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    \$\begingroup\$ This is a simple variant of Textual maze solver \$\endgroup\$ – Peter Taylor May 29 '14 at 11:39
  • \$\begingroup\$ Based on your other examples the coordinates to point B in your very first example should be 7 3. \$\endgroup\$ – Howard May 29 '14 at 11:42
  • \$\begingroup\$ @PeterTaylor I couldn't find that one while I was searching for similars. I would say it is quite different although. The maps can be faulty and the points can be anywhere inside the map, along with other minor differences. \$\endgroup\$ – seequ May 29 '14 at 12:02
  • 1
    \$\begingroup\$ The Textual Maze Solver is not the same as this. In that question the shortest path is not required and it requires output in a different format. Could someone mind explaining why this is a duplicate? \$\endgroup\$ – seequ May 29 '14 at 12:19
  • \$\begingroup\$ @TheRare The format of the input and output are not enough to convince me that a challenge is not duplicate, unless converting the input or output poses a significant challenge in itself. I don't know about the Maze challenge, but finding the shortest path on a graph is the heart of this challenge, and a large portion of this one. The rules regarding what makes a duplicate are largely unformalized, so you may have different voting criteria. \$\endgroup\$ – Rainbolt May 29 '14 at 15:42

Browse other questions tagged or ask your own question.