I'm trying to find vertical paths of length n through a 2D grid of numbers. Paths may connect orthogonally or diagonally. An example grid and an example possible path looks like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
//Grid
0 1 2 3 4 5 6 7
0 2 4 6 4 1 3 4 5
1 5 3 5 8 6 6 6 6
2 3 4 2 1 1 2 5 3
3 3 2 3 3 1 3 4 5
4 3 6 1 1 5 2 5 4
5 2 5 4 2 4 5 6 2
6 6 6 1 1 5 1 4 5
7 1 5 6 4 2 4 2 3
A example possible path of length n = 3 is running from (3,2) to (3,4) - All 1s
Edit: An example of n = 4 is the run of 3s (1,1) (0,2) (0,3), (0,4)
What is an efficient algorithm for solving this kind of problem? I would like to solve (ideally) millions of grids, giving a list for each grid of all possible paths of length for n = 3-6.
All paths of n = 3, n = 4, n = 5, n = 6. The thing is, I could just look at every node and find every path, but that is very expensive! It feels like there should be some kind of way to make that substantially more efficient? I can't think how though. =/
Total number of paths for n = 3 : 3
Total number of paths for n = 4 : 1
Total number of paths for n = 5 : 0
Total number of paths for n = 6 : 1
Where the n = 3 paths are any path you can connect through orthogonally or diagonally that traverses at least 3 vertical levels, a n = 4 path connects 4 vertical levels etc...
You don't have to search the whole grid every time. You can initially copy the data stored in the grid into arrays of x,y positions of each number 1, 2, 3, etc. Then, when trying to find paths of a certain number, you are limiting the search to only that certain number, ignoring the rest.
You can use easily recursion, running from i=0 to n-1 and j=0 to m-1,
assume a new array B contain 0s size = A's.
if B[i][j] = 0 then process A[i][j], which function is checking for the same value as A[i][j] around (i,j) by recursive. And after check, you'll know how many of them around, put it on all of B[-][-] you run through.
You can initially copy the data stored in the grid into arrays of x,y positions of each number 1, 2, 3, etc.
One variant of this:
-Reserve a vector for N*M pairs (value,count).
-Create a N*M matrix B of pointers to those pairs.
-Iterate your data matrix.
A(i,j) has value
IF any in A(i-1,j-1), A(i,j-1), A(i+1,j-1) has same value
THEN set B(i,j) to point to existing pair** and increment the count of that pair
ELSE append new pair(value,1) and set B(i,j) to point to it.
**If there are more than one existing pair, then point to the one with largest count.
Now the vector has list of paths, but it only knows value and length for each path.
Replace the count with a list of x,y pairs. Length of list is still the count, but now you know the elements of each path.
You still have a problem with the Y-shaped paths. For example, there is a path of 3 and path of 4 that both are elongated by A(i,j) (into 4 and 5). My algorithm would leave the 3 as 3 and turn the 4 into 5 (and potentially more, if lower rows continue it).