StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think you should do a <a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow">DFS</a> with memory of the followed path. In pseudocode, it would look like this:</p> <pre><code>DFS(matrix, path): /* End conditions */ If path.last is [n-1, n-1] print path /* Hooray! Found a path! */ If path.last has already been visited in path Discard solution If path.last is out of bounds (coordinates < 0 or > n-1) Discard solution If matrix[path.last] value is 0 Discard solution /* We're in the middle of a path: continue exploring */ For direction in [1, 0], [0, 1], [-1, 0], [0, -1] Add [path.last + direction] to path // Move north, south, east, west DFS(matrix, path) Remove last element from path /* Call the algorithm */ DFS(matrix, [1, 1]) </code></pre> <p>In this algorithm, you can pass around references to matrix and path, which gives you a constant memory algorithm (you have only one instance of <code>path</code> around). As for time complexity, this would be linear on the <strong>number of possible paths</strong> (because you explore each possible path once, even dismissed ones), and quadratic on their <strong>length</strong> (because you test, for each point, if it is already present in the path with linear search). Keep in mind that the <strong>number of paths can me exponential on</strong> <code>n</code>, and that the length of a path is, worst case, <code>n^2</code>. Very slow brute force algorithm.</p> <p>The <strong>worst case</strong> for this algorithm would be a matrix filled with only ones with exponential complexity.</p> <p>The <strong>best case</strong> would be a matrix with only one possible path between <code>[1, 1]</code> and <code>[n-1, n-1]</code>. In that case, you have a complexity on the length of the path, which can be between <code>O(n)</code> and <code>O(n^2)</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload