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