Самый длинный путь 1 в матрице

Question

Учитывая двумерную булеву матрицу, в которой мы можем путешествовать во всех 8 направлениях, как мы можем найти максимальную длину пути 1 в ней. Легко найти самый большой регион 1, но я хочу найти самый большой путь 1 в нем. Путь после посещения не должен быть посещен снова. Движение в любом направлении считается одним шагом. Например:

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

Здесь самый большой регион - 8, но самый длинный путь - 6. Как бы мы это сделали?

Answer 1

Постройте неориентированный граф на основе вашей матрицы: каждая ячейка «1» является узлом, и между каждой парой соседних ячеек «1» есть ребро.

Теперь найдите самый длинный путь на графике.