因为数据范围\(n,m \leq 20\)，可以考虑爆搜。
使用dfs遍历所有路径，若路径合法，则令答案加一。
可以令dfs维护当前经历过的为0的节点的数量，记做depth，其中grid中含有的0节点的总数为cnt，如果depth == cnt && grid[x][y] == 2，那么说明我们找到了一条合法路径，令答案加一。
class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid)
{
int n = grid.size(), m = grid[0].size();
constexpr int dx[4] = {0, 1, 0, -1};
constexpr int dy[4] = {-1, 0, 1, 0};
int cnt = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (grid[i][j] == 0)
++cnt;
int res = 0;
vector<vector<int>> st(n, vector<int>(m));
function<void(int, int, int)> dfs = [&] (int x, int y, int depth)
{
st[x][y] = true;
for (int i = 0; i < 4; ++i)
{
int sx = x + dx[i], sy = y + dy[i];
if (sx >= 0 && sx < n && sy >= 0 && sy < m && !st[sx][sy] && grid[sx][sy] != -1)
dfs(sx, sy, depth + (grid[sx][sy] == 0));
}
st[x][y] = false;
if (grid[x][y] == 2 && cnt == depth)
++res;
};
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (grid[i][j] == 1)
{
dfs(i, j, 0);
break;
}
return res;
}
};