Проблема дня Leetcode [31 декабря 2022 г.]
Вам дан массив целых чисел m x n
grid
, где grid[i][j]
может быть:
1
представляет начальную клетку. Существует ровно одна начальная клетка.2
представляет конечный квадрат. Есть ровно один конечный квадрат.0
представляет собой пустые квадраты, по которым мы можем пройти.-1
представляют собой препятствия, которые мы не можем преодолеть.
Возвращает количество обходов в четырех направлениях от начального квадрата к конечному квадрату, которые проходят все квадраты без препятствий ровно один раз.
Пример 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)
Пример 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)
Пример 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.
Решение
Проблема та же, что и при поиске уникальных путей, которые мы можем найти с помощью DFS (поиск в глубину). но есть только один поворот, и это то, что мы должны пройти все пустые ячейки.
Итак, сначала мы подсчитываем пустые ячейки, и когда мы достигаем конечного пункта назначения, мы проверяем, равно ли количество пустых ячеек 0 или нет.
Как только мы покидаем ячейку, мы помечаем ее как непосещенную и увеличиваем пустые ячейки на 1.
class Solution { public int uniquePathsIII(int[][] grid) { int totalEmptyCells = 0; int startRow = -1; int startCol = -1; for(int i=0;i<grid.length;i++) { for(int j=0;j<grid[0].length;j++) { if(grid[i][j] == 1) { startRow = i; startCol = j; } else if(grid[i][j] == 0) totalEmptyCells++; } } return countPaths(grid, startRow, startCol, totalEmptyCells); } public int countPaths(int[][] grid, int startRow, int startCol, int totalEmptyCells) { int m = grid.length; int n = grid[0].length; boolean[][] visited = new boolean[m][n]; return dfs(grid, startRow, startCol, m, n, visited, totalEmptyCells+1); } public int dfs(int[][] grid, int i, int j, int m, int n, boolean[][] visited, int totalEmptyCells) { if(i < 0 || j < 0 || i >= m || j >= n) return 0; if(grid[i][j] == -1) return 0; // blocker if(visited[i][j]) return 0; // already visited if(grid[i][j] == 2) { // reached finish state if(totalEmptyCells == 0) return 1; return 0; } visited[i][j] = true; totalEmptyCells--; int ans = 0; ans += dfs(grid, i+1, j, m, n, visited, totalEmptyCells); ans += dfs(grid, i-1, j, m, n, visited, totalEmptyCells); ans += dfs(grid, i, j+1, m, n, visited, totalEmptyCells); ans += dfs(grid, i, j-1, m, n, visited, totalEmptyCells); totalEmptyCells++; visited[i][j] = false; return ans; } }
Присоединяйтесь к моему каналу Telegram, чтобы получать ежедневные решения Leetcode Challenge.
Спасибо всем!!!
С Новым Годом #2023