Path finding in a multidimensional array

Question

I sort of understand the concept of pathfinding and how a program looks for point B from point A in the most efficient manner and vaguely familiar with the concept of A*. But what if, instead of trying to find a way through the maze, you're trying to find the longest corridor in closed off maze where the corridor can not be on a diagonal.

Here's my example maze:

1 1 0 1
0 0 1 1
1 0 1 0
1 0 1 0

If using 1's as the allowed path and 0's as an invalid path, the longest path is 5 with the coordinates being (0,3), (1,2), (1,3), (2,2), (3,2).

How would I find this information recursively?

I've been racking my brain on how to start from (0,0) and go up, down, left, right to see if those are possible moves, but any version I come up with encounters duplicates and repeated counts.

Answer 1

I would look at a flood fill algorithm.

Basically start at the first 1 - flood fill from there, and count the filled positions. Set those to 0 (even as you go), and repeat.

I think there are ways to parallelize this exact problem as well.

Answer 2

You can represent the array as graph (when the 1s are the vertices and two vertices are connected if their corresponding 1s are adjacent.
Then find the diameter of the graph. (the diameter is the longest path).
Take a look here for how to find the diameter.

Answer 3

DFS is exactly what you want. The code must look like:

int[,] map = InitTheMapHere();
int longest = -1;
int currentLength = 0;
void TryStep(int x,int y)
{
   if (map[x][y]==0 or over the edge)  //update the longest and return

      TryStep(go up);
      TryStep(go down);
      TryStep(go left);
      TryStep(go right);
}