leetcode Daily Challenge on September 20th, 2020.
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.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)
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)
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.
1 <= grid.length * grid[0].length <= 20
- mine
-
Java
-
DFS
Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.7 MB, less than 33.33% of Java online submissions
got from the most votes
//emptyCount = 1, is mean the ending square public int res = 0,sX,sY,eX,eY,emptyCount = 1; public int uniquePathsIII(int[][] grid) { calculate(grid); dfs(grid,sX,sY); return res; } public void calculate(int[][] grid){ for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[i].length; j++){ if(grid[i][j] == 1){ sX = i; sY = j; }else if(grid[i][j] == 2){ eX = i; eY = j; }else if(grid[i][j] == 0){ emptyCount++; } } } } public void dfs(int[][] grid, int x, int y) { if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] < 0) return; if (x == eX && y == eY) { if (emptyCount == 0) res++; return; } grid[x][y] = -2;// As long as it is not -1, 0, 1, 2 emptyCount--; dfs(grid, x + 1, y); dfs(grid, x - 1, y); dfs(grid, x, y + 1); dfs(grid, x, y - 1); grid[x][y] = 0; emptyCount++; }
-
-
-
the most votes
- DFS
Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.4 MB, less than 33.33% of Java online submissions
int res = 0, empty = 1, sx, sy, ex, ey; public int uniquePathsIII(int[][] grid) { int m = grid.length, n = grid[0].length; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 0) empty++; else if (grid[i][j] == 1) { sx = i; sy = j; } else if (grid[i][j] == 2) { ex = i; ey = j; } } } dfs(grid, sx, sy); return res; } public void dfs(int[][] grid, int x, int y) { if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] < 0) return; if (x == ex && y == ey) { if (empty == 0) res++; return; } grid[x][y] = -2; empty--; dfs(grid, x + 1, y); dfs(grid, x - 1, y); dfs(grid, x, y + 1); dfs(grid, x, y - 1); grid[x][y] = 0; empty++; }
- DFS