Проблема дня 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.



ЕДИНСТВЕННЫЙ МАСТЕР | КОДИРОВАНИЕ
кодирование #программирование #leetcode #codechef #hackerrank #interviewbit #gfgt.me



Спасибо всем!!!

С Новым Годом #2023