Number of `m` length walks from a vertice with steps in [1, s]

Question

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];
}

Answer 1

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.