# 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. 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::pair<size_t, size_t>;

auto hash_pair = [](const Cord& c)
{
return std::hash<size_t>{}(c.first) ^ (std::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.size(); i++) {
for (size_t j=0; j < board.size(); j++) {
if (board[i][j] == 'L')
{
return make_pair(i, j);
}
}
}
return make_pair(-1, -1);
}

NeighborsMap BuildNeighbors(const vector<string>& board, size_t s)
{
NeighborsMap neighbors(board.size() * board.size(), hash_pair);

for (size_t i = 0; i < board.size(); i++)
{
for (size_t j = 0; j < board.size(); j++)
{
size_t min_i = i > s ? i - s : 0;
size_t max_i = i + s > board.size() - 1 ? board.size() - 1 : i + s;
size_t min_j = j > s ? j - s : 0;
size_t max_j = j + s > board.size() - 1 ? board.size() - 1 : j + s;

auto key = make_pair(i, j);

if (board[i][j] != 'P')
{
for (size_t x = min_i; x <= max_i; x++)
{
if (board[x][j] != 'P' && x != i)
{
neighbors[key].push_back(make_pair(x, j));
}
}

for (size_t y = min_j; y <= max_j; y++)
{
if (board[i][y] != 'P' && y != j)
{
neighbors[key].push_back(make_pair(i, y));
}
}
neighbors[key].push_back(key);
}
else
{
neighbors[key].clear();
}
}
}

return neighbors;
}

int GetNeighboursWalks(const Cord& cord, NeighborsMap& neighbors, const vector<vector<int>>& prevBoard)
{
int sum{ 0 };
const auto& currentNeighbors = neighbors[cord];
for (const auto& neighbor : currentNeighbors)
{
sum += prevBoard[neighbor.first][neighbor.second];
}
return sum;
}

int findWalks(int m, int s, vector<string> board) {
vector<vector<int>> currentBoard = initBoard(board.size());
vector<vector<int>> prevBoard = initBoard(board.size());
std::unordered_map<int, std::vector<Cord>> progress;

auto poi = findPOI(board);
NeighborsMap neighbors = BuildNeighbors(board, s);
for (const auto& item : neighbors)
{
const auto& key = item.first;
const auto& value = item.second;
prevBoard[key.first][key.second] = value.size();
}

for (size_t k = 1; k <= static_cast<size_t>(m); k++)
{
for (size_t i = 0; i < board.size(); i++)
{
for (size_t j = 0; j < board.size(); j++)
{
auto currentKey = make_pair(i, j);
currentBoard[i][j] = board[i][j] != 'P' ? GetNeighboursWalks(currentKey, neighbors, prevBoard) : 0;
}
}

std::swap(currentBoard, prevBoard);
}
return prevBoard[poi.first][poi.second];
}


Let $$A$$ be the set of available vertices (including $$L$$) and let $$A(v)$$ be the set of available vertices reachable by $$v$$ with a single move.

Let $$M[v,\ell]$$ be the number of walks of length exactly $$\ell \ge 0$$ from vertex $$v \in A$$.

You have that:

• $$M[v,0] = 1 \quad \forall v \in A$$;
• $$M[v,\ell] = \sum_{u \in A(v)} M[u,\ell-1] \quad \forall v \in A, \forall \ell > 0$$.

Intuitively, the second bullet means that every walk $$\langle v, u, w_1, w_2, \dots \rangle$$ of length $$\ell$$ from $$v$$ can be decomposed into an initial move to a vertex $$u$$ in $$A(v)$$, plus the walk $$\langle u, w_1, w_2, \dots \rangle$$ which has length $$\ell-1$$ and starts from $$u$$. The converse is also true (that is, if you have a walk $$\langle u, w_1, w_2, \dots \rangle$$ of length $$\ell-1$$ from a vertex $$u \in A(v)$$, then this also induces the walk $$\langle v, u, w_1, w_2, \dots \rangle$$ of length $$\ell$$ from $$A(v)$$). Since, by definition of $$M[\cdot, \cdot]$$, there are exactly $$M[u,\ell-1]$$ walks of length $$\ell-1$$ from $$u \in A(v)$$, it follows that the overall number of walks of length $$\ell$$ from $$v$$ is exactly the one given in the formula.

The value you are looking for is exactly $$M[L, \ell]$$.

Computing all sets $$A(v)$$ takes time $$O(|A| s^2)$$. Once this is done, computing each of the $$O(|A| \ell)$$ values $$M[v,\ell]$$ takes time $$O(|A(v)|) = O(s^2)$$. This leads to a dynamic programming algorithm requiring $$O(|A| \ell s^2)$$ time.

• Thanks, Steven I was wondering what I missed in my assumptions, at first glance it seems that you too have step in which we're creating a set of all reachable $v'$ from $v$ and then a summation for every reachable $v'$ from $v$ using the previous $l$, so I might be missing some difference. Also could you please provide a little more detail about the rationale of each step you mention ? Mar 12, 2020 at 19:19
• There are a few typos in your question so it's hard for me to fully understand it and point out what you are doing wrong. Could you give a precise definition of what you're storing in $M[i][j]$? I have now commented on the second bullet. I think it was the only step that was not immediately clear. Mar 12, 2020 at 19:42
• I think the main difference is that your solution has the sum go for $M[v,\ell] = \sum_{u \in A(v)} M[u,\ell-1] \quad \forall v \in A, \forall \ell > 0$ and mine Has $M[i,j] = \sum_{u \in A(v)} M[u,\ell-1] \quad \forall v \in A$ Meaning I'm only reaching to the paths length $l-1$ and not all of $l-1, l-2, \dots , 1$ Mar 12, 2020 at 20:26
• I also tried to clarify my iteration steps Mar 12, 2020 at 20:48
• There are still some issues, e.g., $i$ refers to 2 different things in $M_i[i,j]$. Anyway, it looks like you want to define $M_k[i,j]$ as the number of walks of length exactly $k$ from $L$ to the vertex at coordinates $(i,j)$. If this is the case then the idea behind your approach would work. You need to be careful in your base case, it seems that you are computing $M_1[\cdot,\cdot]$ instead of $M_0[\cdot,\cdot]$. Also, the final answer is the sum of $M_m[i,j]$ over all $(i,j)$. A final detail: according to your definition of move, $L$ is a neighbor of itself. I'm not sure if this is intended. Mar 12, 2020 at 21:46