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
My code:
class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
int ans;
pair<int, int> start, end;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1)
start = {i, j};
if (grid[i][j] == 2)
end = {i, j};
}
}
helper(grid, start, end);
return ans;
}
private:
int ans = 0;
void helper(const vector<vector<int>>& grid, const pair<int, int>& start, const pair<int, int>& end) {
vector<vector<int>> temp = grid;
int startX = start.first;
int startY = start.second;
// cout << start.first << " " << start.second << endl;
// cout << end.first << " " << end.second << endl;
dfs(temp, startX+1, startY, end);
dfs(temp, startX-1, startY, end);
dfs(temp, startX, startY+1, end);
dfs(temp, startX, startY-1, end);
}
void dfs(vector<vector<int>> temp, int curX, int curY, const pair<int, int>& end) {
if (curX == end.first && curY == end.second && check(temp)) ans++, return;
if (curX < 0 || curX >= temp.size() || curY < 0 || curY >= temp[0].size() || temp[curX][curY] != 0) return;
// cout << curX << " " << curY << endl;
temp[curX][curY] = 3;
dfs(temp, curX+1, curY, end);
dfs(temp, curX-1, curY, end);
dfs(temp, curX, curY+1, end);
dfs(temp, curX, curY-1, end);
}
bool check(vector<vector<int>>& temp) {
for (int i = 0; i < temp.size(); ++i) {
for (int j = 0; j < temp[0].size(); ++j) {
if (temp[i][j] == 0) return false;
}
}
return true;
}
};
/*
[[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]]
*/
Approach #2: DFS. [C++]
class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
int num = 1;
int sx = -1, sy = -1;
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j)
if (grid[i][j] == 0) num++;
else if (grid[i][j] == 1) sx = i, sy = j;
return dfs(grid, sx, sy, num);
}
private:
int dfs(vector<vector<int>>& grid, int cx, int cy, int num) {
if (cx < 0 || cx >= grid.size() || cy < 0 || cy >= grid[0].size() || grid[cx][cy] == -1) return 0;
if (grid[cx][cy] == 2) return num == 0;
grid[cx][cy] = -1;
int path = dfs(grid, cx+1, cy, num-1)+
dfs(grid, cx-1, cy, num-1)+
dfs(grid, cx, cy+1, num-1)+
dfs(grid, cx, cy-1, num-1);
grid[cx][cy] = 0;
return path;
}
};
Analysis:
In the first code. I don‘t get the correct answer. Maybe my thinking is wrong in this problem.
原文：https://www.cnblogs.com/ruruozhenhao/p/10356962.html