Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/3c3be2671ef16ab2db2dc4575a855d32 to your computer and use it in GitHub Desktop.
Save jianminchen/3c3be2671ef16ab2db2dc4575a855d32 to your computer and use it in GitHub Desktop.
Search a path with increasing value given two nodes
Problem statement:
you are given a matrix. Size m rows, n columns. start point and end point.
try to find a path from start point to end point, in the path, the next value is bigger then the previous value.
Every time you can go four directions, left, top, right and bottom.
For example,
[[1,4,5,3]
[2,4,0,1]
[3,6,8,-1]]
start = [0,0] end [2,2]
==> [0,0], [1,0], [2,0],[2,1], [2,2]
1 2 3 6 8
Julia's analysis:
rows * columns -> length of path
visit - mark visit
DFS/ BFS -> exhaust all options
constraint: next step is bigger than current
shortest path -> no confliction
BFS -> node 1, at most four neighbors -> add neighbors > 1 to queue, mark 1 is visted, prefix 1->
Here is my idea to write a solution:
//int layerIndex = 0;
while(queue.count > 0 )
{
countOfqueue = queue.count; //
deque one by one
{
// check four possible neighbor, unvisited before, see bigger than previous neighbor -> check prefix
if(desitinatian node = )
return path = prefix + add current neighbornode
}
else {
add those node to queuue
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment