Number of `m` length walks from a vertice with steps in [1, s]
The problem is stated as the following:
We are given a grid graph $G$ of $N \times N$, represented by a series of strings that describe vertices s.t.
* $L$ is the vertice we're interested in
* $P$ are vertices that are unavailable
* $.$ are vertices that are available
e.g.:
....
...L
..P.
P...
Would mean a graph that looks like this
0 1 2 3
+-------------------+
0| | | | |
| | | | |
+-------------------+
1| | | | |
| | | | |
+-------------------+
2| | |XXXX| |
| | |XXXX| |
+-------------------+
3|XXXX| | | |
|XXXX| | | |
+-------------------+
Where $v_{2,3}$ and $v_{0,3}$ are unavailable and we're interested in $v_{3,1}$.
From each vertice we're only allowed to move on the axis (we can't move on the diagonal) and a move is valid from $v_{x,y}$ to $v_{q,p}$ if
* $ |x-q| + |y-p| \leq s$ and $v_{q,p}$ is available.
* Staying in the same spot is also a valid move
Given $m$ - maximal number of moves and $s$ what is the number of ways we can make $m$ moves from vertice designated by $L$.
My attempt was to
* First compute the neighbors reachable from each node. Create a look s.t. $\forall v N[v]$ is the list of reachable nodes from $v$
* Then build a starting record $M_0$ s.t. if node is reachable $M[i][j] = 1$ and $0$ otherwise.
* Then for each step calculate for $\forall i,j \in N$ (all the grid) $ M_{i}[i][j] = \sum_{v\in N[v]} M_{i-1}[v_i][v_j]$ (where $v_i, v_j$ are the coordinates of $v$ on the grid) and store in a matrix $M_i$
We iterate until $i==m$.
1. 839
for each $v_{i,j}$: 1. for each neighbor $n$ of $v_{i,j}$: 1. $M[i][j] += M'[n_i][n_j]$
Unfortunately this doesn't work (tried to do it with a pen and paper as well to make sure) and I get fewer results then the expected answer, apparently there should be 385 ways but I only get to 187.
Here are the intermediate states for the above mentioned board:
----------------------------
5 6 5 5
5 7 6 6
4 6 0 5
0 5 4 5
----------------------------
25 34 27 27
27 41 33 34
20 33 0 27
0 27 20 25
----------------------------
133 187 146 149
146 229 182 187
105 182 0 146
0 146 105 133
----------------------------
This did work for e.g. m=2 and s=1 for the following board:
0 1 2
+---+---+---+
0| | | |
| | | |
+-----------+
1| | | |
| | | |
+-----------+
2| | | |
| | | |
+---+---+---+
Here's my reference code (findWalks is the main function)
using namespace std;
using Cord = std<IP_ADDRESS>pair<size_t, size_t>;
auto hash_pair = [](const Cord& c)
{
return std<IP_ADDRESS>hash<size_t>{}(c.first) ^ (std<IP_ADDRESS>hash<size_t>{}(c.second) << 1);
};
using NeighborsMap = unordered_map<Cord, vector<Cord>, decltype(hash_pair)>;
inline vector<vector<int>> initBoard(size_t n)
{
return vector<vector<int>>(n, vector<int>(n, 0));
}
Cord findPOI(vector<string>& board)
{
for (size_t i=0; i < board. 180