Problem
You are given an m x n
integer array grid
where grid[i][j]
could be:
1
representing the starting square. There is exactly one starting square.2
representing the ending square. There is exactly one ending square.0
representing empty squares we can walk over.-1
representing obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
Example 1:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
Example 2:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
Example 3:
Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 20
1 <= m * n <= 20
-1 <= grid[i][j] <= 2
There is exactly one starting cell and one ending cell.
Solution
/**
* @param {number[][]} grid
* @return {number}
*/
var uniquePathsIII = function(grid) {
var start;
var m = grid.length;
var n = grid[0].length;
var emptyNum = 0;
for (var i = 0; i < m; i++) {
for (var j = 0; j < n; j++) {
if (grid[i][j] === 1) start = [i, j];
else if (grid[i][j] === 0) emptyNum++;
}
}
return getPathNum(start[0], start[1], grid, 0, emptyNum);
};
var getPathNum = function(i, j, grid, visitedNum, emptyNum) {
var res = 0;
var directions = [
[1, 0], // up
[-1, 0], // down
[0, -1], // left
[0, 1], // right
];
for (var k = 0; k < 4; k++) {
var [diffX, diffY] = directions[k];
if (grid[i + diffX] && grid[i + diffX][j + diffY] === 0) {
grid[i + diffX][j + diffY] = -1;
res += getPathNum(i + diffX, j + diffY, grid, visitedNum + 1, emptyNum);
grid[i + diffX][j + diffY] = 0;
} else if (grid[i + diffX] && grid[i + diffX][j + diffY] === 2) {
res += (visitedNum === emptyNum ? 1 : 0);
}
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n!).
- Space complexity : O(1).