Created
July 14, 2018 20:12
-
-
Save jianminchen/3c3be2671ef16ab2db2dc4575a855d32 to your computer and use it in GitHub Desktop.
Search a path with increasing value given two nodes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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