Hard

题目描述

给你一个 m x n 的整数数组 grid，其中 grid[i][j] 可能为：

  • 1 表示起始方格。有且只有一个起始方格。
  • 2 表示结束方格。有且只有一个结束方格。
  • 0 表示我们可以走过的空方格。
  • -1 表示我们无法跨越的障碍物。

返回在四个方向（上、下、左、右）上行走从起始方格到结束方格的不同路径数，每一个无障碍方格都要通过一次。

示例 1：

输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
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：

输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径：
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：

输入：grid = [[0,1],[2,0]]
输出：0
解释：没有一条路径能够使我们走过每一个空方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 20
  • 1 <= m * n <= 20
  • -1 <= grid[i][j] <= 2
  • 网格中只有一个起始单元格和一个结束单元格。

解题思路

这道题要求从起始点到终点的路径，且必须经过每一个非障碍方格恰好一次。这是一个典型的回溯问题。

解题思路：

  1. 预处理阶段：遍历网格，找到起始位置、终点位置，并统计需要访问的空格子总数（包括起始点和终点）。

  2. 回溯算法：从起始位置开始进行深度优先搜索：

    • 标记当前位置为已访问（设为-1，表示障碍）
    • 向四个方向尝试移动
    • 如果到达终点且访问了所有必须访问的格子，则找到一条有效路径
    • 回溯时恢复当前位置的原始值

  3. 剪枝优化：

    • 边界检查：确保不越界
    • 障碍检查：不能走到-1的格子
    • 已访问检查：不能重复访问同一格子
    • 路径长度检查：只有当访问的格子数等于总的非障碍格子数时才能到达终点

推荐解法：回溯 + DFS

时间复杂度相对较高，但由于题目限制网格大小不超过20，完全可以接受。这种解法思路清晰，易于理解和实现。

代码实现

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int startX = -1, startY = -1, endX = -1, endY = -1;
        int emptyCount = 0;
        
        // 找到起点、终点，统计需要访问的格子数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    startX = i;
                    startY = j;
                    emptyCount++;
                } else if (grid[i][j] == 2) {
                    endX = i;
                    endY = j;
                    emptyCount++;
                } else if (grid[i][j] == 0) {
                    emptyCount++;
                }
            }
        }
        
        return dfs(grid, startX, startY, endX, endY, emptyCount);
    }
    
private:
    int dfs(vector<vector<int>>& grid, int x, int y, int endX, int endY, int remaining) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == -1) {
            return 0;
        }
        
        if (x == endX && y == endY) {
            return remaining == 1 ? 1 : 0;
        }
        
        int original = grid[x][y];
        grid[x][y] = -1; // 标记为已访问
        
        int paths = 0;
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (auto& dir : directions) {
            int newX = x + dir.first;
            int newY = y + dir.second;
            paths += dfs(grid, newX, newY, endX, endY, remaining - 1);
        }
        
        grid[x][y] = original; // 回溯
        return paths;
    }
};

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        start_x = start_y = end_x = end_y = -1
        empty_count = 0
        
        # 找到起点、终点，统计需要访问的格子数
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    start_x, start_y = i, j
                    empty_count += 1
                elif grid[i][j] == 2:
                    end_x, end_y = i, j
                    empty_count += 1
                elif grid[i][j] == 0:
                    empty_count += 1
        
        def dfs(x, y, remaining):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == -1:
                return 0
            
            if x == end_x and y == end_y:
                return 1 if remaining == 1 else 0
            
            original = grid[x][y]
            grid[x][y] = -1  # 标记为已访问
            
            paths = 0
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_x, new_y = x + dx, y + dy
                paths += dfs(new_x, new_y, remaining - 1)
            
            grid[x][y] = original  # 回溯
            return paths
        
        return dfs(start_x, start_y, empty_count)

public class Solution {
    public int UniquePathsIII(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int startX = -1, startY = -1, endX = -1, endY = -1;
        int emptyCount = 0;
        
        // 找到起点、终点，统计需要访问的格子数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    startX = i;
                    startY = j;
                    emptyCount++;
                } else if (grid[i][j] == 2) {
                    endX = i;
                    endY = j;
                    emptyCount++;
                } else if (grid[i][j] == 0) {
                    emptyCount++;
                }
            }
        }
        
        return DFS(grid, startX, startY, endX, endY, emptyCount);
    }
    
    private int DFS(int[][] grid, int x, int y, int endX, int endY, int remaining) {
        if (x < 0 || x >= grid.Length || y < 0 || y >= grid[0].Length || grid[x][y] == -1) {
            return 0;
        }
        
        if (x == endX && y == endY) {
            return remaining == 1 ? 1 : 0;
        }
        
        int original = grid[x][y];
        grid[x][y] = -1; // 标记为已访问
        
        int paths = 0;
        int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int i = 0; i < 4; i++) {
            int newX = x + directions[i, 0];
            int newY = y + directions[i, 1];
            paths += DFS(grid, newX, newY, endX, endY, remaining - 1);
        }
        
        grid[x][y] = original; // 回溯
        return paths;
    }
}

var uniquePathsIII = function(grid) {
    let startRow = 0, startCol = 0, emptySquares = 0;
    const m = grid.length, n = grid[0].length;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                startRow = i;
                startCol = j;
                emptySquares++;
            } else if (grid[i][j] === 0) {
                emptySquares++;
            }
        }
    }
    
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    function dfs(row, col, remaining) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] === -1) {
            return 0;
        }
        
        if (grid[row][col] === 2) {
            return remaining === 0 ? 1 : 0;
        }
        
        const original = grid[row][col];
        grid[row][col] = -1;
        
        let paths = 0;
        for (const [dr, dc] of directions) {
            paths += dfs(row + dr, col + dc, remaining - 1);
        }
        
        grid[row][col] = original;
        return paths;
    }
    
    return dfs(startRow, startCol, emptySquares);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
回溯搜索O(4^(m×n))O(m×n)

说明：

  • 时间复杂度：最坏情况下需要探索所有可能的路径，每个位置最多有4个方向，总共有m×n个位置
  • 空间复杂度：递归调用栈的深度最多为m×n（访问所有格子），原地修改grid数组不算额外空间

相关题目