1

I have a n by n maze, like this:

[0, 1, 0, 0, 0, 1]
[1, 1, 0, 1, 1, 0]
[1, 0, 0, 1, 0, 1]
[0, 1, 1, 0, 0, 1]
[0, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 1]

Only 0-fields are passable, and one can only move directly up, down, left, or right.

I want to find the longest possible cycle-free path from a given point.

I am aware that there are recursive algorithms for this problem, but I was wondering if there are any more efficient algorithms, or any optimizations to the recursive algorithm that I can use?

gnat
  • 21,442
  • 29
  • 112
  • 288
b_pcakes
  • 119
  • 1
  • 1
    This is equivalent to the [longest-path problem](https://en.m.wikipedia.org/wiki/Longest_path_problem), which is NP-hard. – Jon Purdy Oct 17 '15 at 07:17
  • Since this is constrained to start from a given point, does that give any kind of advantage here? – J Trana Oct 17 '15 at 13:48

0 Answers0