Поиск путей в многомерном массиве

Question

Я как бы понимаю концепцию поиска пути и как программа ищет точку B из точки A наиболее эффективным образом и смутно знакома с понятием A *. Но что, если вместо того, чтобы пытаться найти путь через лабиринт, вы пытаетесь найти самый длинный коридор в закрытом лабиринте, где коридор не может быть по диагонали.

Вот мой пример лабиринт:

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

При использовании 1 в качестве разрешенного пути и 0 как недопустимый путь, самый длинный путь 5 с координатами (0,3, являющихся), (1,2) , (1,3), (2,2), (3,2).

Как я могу найти эту информацию рекурсивно?

Я уже ломаю голову о том, как начать с (0,0) и идти вверх, вниз, влево, вправо, чтобы увидеть, возможны ли эти движения, но в любой версии я встречаю дубликаты и повторные подсчеты ,

Answer 1

Я бы рассмотрел алгоритм flood fill.

Обычно начинаются с первых 1 - заливка оттуда и подсчет заполненных позиций. Установите их на 0 (даже когда вы идете) и повторите.

Я думаю, что есть способы распараллеливать эту точную проблему.

Answer 2

можно представить массив как графа (когда 1s являются вершинами и две вершины соединены, если соответствующие им 1s являются смежными.
затем найти диаметр графа. (Диаметр самый длинный путь).
.. посмотрите here для того, как найти диаметр

Answer 3

DFS это именно то, что вы хотите, код должен выглядеть следующим образом:

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); 
}