On a 2-dimensional grid, there are 4 types of squares:
1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents 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: [[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: [[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: [[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.
Note:
1 <= grid.length * grid[0].length <= 20
Solution:
class Solution {
int num = 0;
int count = 0;
int step = 0;
int[] dx = new int[]{0,1,0,-1};
int[] dy = new int[]{1,0,-1,0};
public int uniquePathsIII(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int x = -1, y = -1, ex = -1, ey = -1;
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
if (grid[i][j] == 1) {
x = i;
y = j;
}
if (grid[i][j] == 2) {
ex = i;
ey = j;
}
if (grid[i][j] == 0) {
count ++;
}
}
}
grid[x][y] = -1;
bt(grid, x, y, ex, ey);
return num;
}
private void bt(int[][] grid, int i, int j, int ex, int ey) {
int m = grid.length;
int n = grid[0].length;
for (int k = 0; k < 4; k ++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] == -1) {
continue;
}
if (ex == nx && ey == ny && step == count) {
num ++;
return;
}
grid[nx][ny] = -1;
step ++;
bt(grid, nx, ny, ex, ey);
step --;
grid[nx][ny] = 0;
}
}
}