← Static tasks

980. Unique Paths III

leetcode hard

#array#backtracking#csharp#hard#leetcode#matrix#tree

Task

Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть:

1, представляющая начальную клетку. Существует ровно одна начальная клетка.

2, представляющая конечную клетку. Существует ровно одна конечная клетка.

0, представляющая пустые клетки, по которым можно ходить.

-1, представляющая препятствия, по которым нельзя ходить.

Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз.

Пример:

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)

C# solution

matched/original
public class Solution {
    private int rows, cols;
    private int[,] grid;
    private int pathCount;
    private void Backtrack(int row, int col, int remain) {
        if (grid[row, col] == 2 && remain == 1) {
            pathCount += 1;
            return;
        }
        int temp = grid[row, col];
        grid[row, col] = -4;
        remain -= 1;
        int[] rowOffsets = {0, 0, 1, -1};
        int[] colOffsets = {1, -1, 0, 0};
        for (int i = 0; i < 4; ++i) {
            int nextRow = row + rowOffsets[i];
            int nextCol = col + colOffsets[i];
            if (0 > nextRow || nextRow >= rows || 0 > nextCol || nextCol >= cols)
                continue;
            if (grid[nextRow, nextCol] < 0)
                continue;
            Backtrack(nextRow, nextCol, remain);
        }
        grid[row, col] = temp;
    }
    public int UniquePathsIII(int[,] grid) {
        int nonObstacles = 0, startRow = 0, startCol = 0;
        rows = grid.GetLength(0);
        cols = grid.GetLength(1);
        this.grid = grid;
        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col) {
                int cell = grid[row, col];
                if (cell >= 0)
                    nonObstacles += 1;
                if (cell == 1) {
                    startRow = row;
                    startCol = col;
                }
            }
        pathCount = 0;
        Backtrack(startRow, startCol, nonObstacles);
        return pathCount;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int rows, cols;
    private int[,] grid;
    private int pathCount;
    private void Backtrack(int row, int col, int remain) {
        if (grid[row, col] == 2 && remain == 1) {
            pathCount += 1;
            return;
        }
        int temp = grid[row, col];
        grid[row, col] = -4;
        remain -= 1;
        vector<int>& rowOffsets = {0, 0, 1, -1};
        vector<int>& colOffsets = {1, -1, 0, 0};
        for (int i = 0; i < 4; ++i) {
            int nextRow = row + rowOffsets[i];
            int nextCol = col + colOffsets[i];
            if (0 > nextRow || nextRow >= rows || 0 > nextCol || nextCol >= cols)
                continue;
            if (grid[nextRow, nextCol] < 0)
                continue;
            Backtrack(nextRow, nextCol, remain);
        }
        grid[row, col] = temp;
    }
    public int UniquePathsIII(int[,] grid) {
        int nonObstacles = 0, startRow = 0, startCol = 0;
        rows = grid.GetLength(0);
        cols = grid.GetLength(1);
        this.grid = grid;
        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col) {
                int cell = grid[row, col];
                if (cell >= 0)
                    nonObstacles += 1;
                if (cell == 1) {
                    startRow = row;
                    startCol = col;
                }
            }
        pathCount = 0;
        Backtrack(startRow, startCol, nonObstacles);
        return pathCount;
    }
}

Java solution

matched/original
class Solution {
    int rows, cols;
    int[][] grid;
    int path_count;

    protected void backtrack(int row, int col, int remain) {
        if (this.grid[row][col] == 2 && remain == 1) {
            this.path_count += 1;
            return;
        }

        int temp = grid[row][col];
        grid[row][col] = -4;
        remain -= 1;

        int[] row_offsets = {0, 0, 1, -1};
        int[] col_offsets = {1, -1, 0, 0};
        for (int i = 0; i < 4; ++i) {
            int next_row = row + row_offsets[i];
            int next_col = col + col_offsets[i];

            if (0 > next_row || next_row >= this.rows || 0 > next_col || next_col >= this.cols)
                continue;

            if (grid[next_row][next_col] < 0)
                continue;

            backtrack(next_row, next_col, remain);
        }

        grid[row][col] = temp;
    }

    public int uniquePathsIII(int[][] grid) {
        int non_obstacles = 0, start_row = 0, start_col = 0;

        this.rows = grid.length;
        this.cols = grid[0].length;

        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col) {
                int cell = grid[row][col];
                if (cell >= 0)
                    non_obstacles += 1;
                if (cell == 1) {
                    start_row = row;
                    start_col = col;
                }
            }

        this.path_count = 0;
        this.grid = grid;

        backtrack(start_row, start_col, non_obstacles);

        return this.path_count;
    }
}

Python solution

matched/original
class Solution:
    def uniquePathsIII(self, grid: list[list[int]]) -> int:
        def backtrack(row, col, remain):
            if grid[row][col] == 2 and remain == 1:
                self.path_count += 1
                return

            temp = grid[row][col]
            grid[row][col] = -4
            remain -= 1

            for ro, co in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                next_row, next_col = row + ro, col + co

                if 0 <= next_row < self.rows and 0 <= next_col < self.cols and grid[next_row][next_col] >= 0:
                    backtrack(next_row, next_col, remain)

            grid[row][col] = temp

        non_obstacles = 0
        start_row = start_col = 0

        self.rows, self.cols = len(grid), len(grid[0])

        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] >= 0:
                    non_obstacles += 1
                if grid[row][col] == 1:
                    start_row, start_col = row, col

        self.path_count = 0
        backtrack(start_row, start_col, non_obstacles)

        return self.path_count

Go solution

matched/original
type Solution struct {
    rows, cols int
    grid       [][]int
    pathCount  int
}

func (s *Solution) backtrack(row, col, remain int) {
    if s.grid[row][col] == 2 && remain == 1 {
        s.pathCount++
        return
    }

    temp := s.grid[row][col]
    s.grid[row][col] = -4
    remain--

    rowOffsets := []int{0, 0, 1, -1}
    colOffsets := []int{1, -1, 0, 0}
    for i := 0; i < 4; i++ {
        nextRow := row + rowOffsets[i]
        nextCol := col + colOffsets[i]

        if nextRow < 0 || nextRow >= s.rows || nextCol < 0 || nextCol >= s.cols {
            continue
        }

        if s.grid[nextRow][nextCol] < 0 {
            continue
        }

        s.backtrack(nextRow, nextCol, remain)
    }

    s.grid[row][col] = temp
}

func (s *Solution) UniquePathsIII(grid [][]int) int {
    nonObstacles, startRow, startCol := 0, 0, 0

    s.rows = len(grid)
    s.cols = len(grid[0])

    for row := 0; row < s.rows; row++ {
        for col := 0; col < s.cols; col++ {
            cell := grid[row][col]
            if cell >= 0 {
                nonObstacles++
            }
            if cell == 1 {
                startRow = row
                startCol = col
            }
        }
    }

    s.pathCount = 0
    s.grid = grid

    s.backtrack(startRow, startCol, nonObstacles)

    return s.pathCount
}

Explanation

Algorithm

1⃣Как видно, метод обратного отслеживания (backtracking) является методологией для решения определенного типа задач.

2⃣Для задачи обратного отслеживания можно сказать, что существует тысяча реализаций обратного отслеживания на тысячу людей, как будет видно из дальнейшей реализации.

3⃣Здесь мы просто покажем один пример реализации, следуя псевдокоду, показанному в разделе интуиции.

😎