2

I have a problem with a C program, where a 2D array with mines is given (mines = array fields set to 1). I need to find the shortest path from (0,0) to (x-1,y-1), and you can move only in 4 directions (up, down, left, right).

Do you have any ideas, what the algorithm should look like to keep the program fairly simple?

Tom Zych
  • 13,329
  • 9
  • 36
  • 53
Nick Jay
  • 31
  • 3
  • Read about [dynamic programming](http://en.wikipedia.org/wiki/Dynamic_programming). – haccks Jun 29 '14 at 11:57
  • What is the proportion of number of mines vs. free tiles? – Jongware Jun 29 '14 at 11:58
  • The user decides the proportion in which at the beginning of the program the user enters all the coordinates of the mines. – Nick Jay Jun 29 '14 at 12:00
  • Is there always a path the player can take to reach the destination? – PandaConda Jun 29 '14 at 12:02
  • No, if the mines are in a uncomfortable way set, there is no solution. – Nick Jay Jun 29 '14 at 12:09
  • see my answer here. basically you can use graph traversal, bfs to be specific. http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/25902381?noredirect=1#comment40579060_25902381 – Viren Sep 19 '14 at 04:49

3 Answers3

3

A* and Dijkstra are more complicated than you need for this problem because, in the graph you are searching, all edges (steps between grid squares) have weight 1.

Just use Breadth First Search:

Let Q be a queue of (x,y) pairs
Let V be a set of (x,y) pairs.
Add the start point (x0,y0) to Q.
While Q is not empty
  H = Q.get_head
  for each neighbor pair N of H in the grid
    if N is not in V
      add N to V
      if N is the goal
        Return N. The path is the chain of N.prev references
      N.prev = H
      Q.add_to_tail(N)
Return "goal could not be reached"
Gene
  • 46,253
  • 4
  • 58
  • 96
0

Use Dijikstra's Algorithm. It will solve the problem in O(x*y) time

Vijay Kansal
  • 809
  • 12
  • 26
0

You can also try A-Star (see wikipedia entry). It is an extension of Dijkstra's algorithm, it's worst-case running time is O(|E|), but can be improved by using heuristics. A-Star will find the lowest cost path through the area, and in your case the cost that you will be using will be the total distance traveled.

Given your limitation on movement, you would probably be best served by using a 'manhattan-distance' heuristic.

thurizas
  • 2,473
  • 1
  • 14
  • 15