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.
- new solution update 2022.02.15
- Time : O(n)
- Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& ob) {
int n = ob.size(), m = ob[0].size();
if(ob[0][0] == 1 or ob[n-1][m-1] == 1) return 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++)
if(ob[i][j] == 1) ob[i][j] = -1;
}
for(int i = 0; i < m and ob[0][i] == 0; i++) ob[0][i] = 1;
for(int i = 1; i < n and ob[i][0] == 0; i++) ob[i][0] = 1;
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
if(ob[i][j] == -1) continue;
ob[i][j] = (ob[i-1][j] == -1 ? 0 : ob[i-1][j]) + (ob[i][j-1] == -1 ? 0 : ob[i][j-1]);
}
}
return ob[n-1][m-1];
}
};
- Time : O(n)
- Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class Solution {
pair<int, int> start, end;
int route = 2, n, m;
vector<vector<bool>> v;
int dx[4]{0,1,0,-1}, dy[4]{-1,0,1,0};
int dfs(int y, int x, int path) {
if(y == end.first && x == end.second) return path == route;
v[y][x] = true;
int res(0);
for(int i = 0; i < 4; i++) {
int ny(y + dy[i]), nx(x + dx[i]);
if(0 <= ny && ny < n && 0 <= nx && nx < m && !v[ny][nx]) {
res += dfs(ny, nx, path + 1);
}
}
v[y][x] = false;
return res;
}
public:
int uniquePathsIII(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size(), v = vector<vector<bool>>(n, vector<bool>(m, false));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 1) start = {i, j};
else if(grid[i][j] == 2) end = {i, j};
else if(!grid[i][j]) route++;
else v[i][j] = true;
}
}
return dfs(start.first, start.second, 1);
}
};