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$ .

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