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

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

Я бы посмотрел на алгоритм заливки .

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

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

Answer 2

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

Answer 3

Вы можете представить массив в виде графа (когда 1 - это вершины и две вершины соединены, если их соответствующие 1 смежны.
Затем найдите диаметр графа (диаметр - самый длинный путь).
Взгляните здесь , чтобы узнать, как найти диаметр.