LeetCode 980. 不同路径 III

Categories:

题目描述
思路分析
1. 解法一：回溯搜索（推荐）
相似题目

题目描述

✅ 980. 不同路径 III

思路分析

解法一：回溯搜索（推荐）

核心思路：

统计可走格子总数 total（含起点与终点）。

从起点 DFS，每走一步将格子标记为已访问并减少剩余可走数。

走到终点时，若剩余可走数为 1，说明恰好覆盖全部格子，计数加一。

复杂度分析：

时间复杂度：O(4^(m*n))，其中 m、n 表示网格尺寸。

空间复杂度：O(m*n)，其中栈深与标记使用的空间规模与网格大小有关。

class Solution {
    private int rows;
    private int cols;
    private int total;
    private int result;

    public int uniquePathsIII(int[][] grid) {
        rows = grid.length;
        cols = grid[0].length;

        int startRow = 0;
        int startCol = 0;
        total = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] != -1) {
                    total++;
                }
                if (grid[i][j] == 1) {
                    startRow = i;
                    startCol = j;
                }
            }
        }

        dfs(grid, startRow, startCol, total);
        return result;
    }

    private void dfs(int[][] grid, int row, int col, int remain) {
        if (grid[row][col] == 2) {
            if (remain == 1) {
                result++;
            }
            return;
        }

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

        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        // 枚举四个方向继续搜索
        for (int k = 0; k < 4; k++) {
            int nr = row + dr[k];
            int nc = col + dc[k];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                continue;
            }
            if (grid[nr][nc] == -1) {
                continue;
            }
            dfs(grid, nr, nc, remain - 1);
        }

        grid[row][col] = temp;
    }
}

func uniquePathsIII(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	total := 0
	startRow, startCol := 0, 0
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if grid[i][j] != -1 {
				total++
			}
			if grid[i][j] == 1 {
				startRow, startCol = i, j
			}
		}
	}

	result := 0
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

	var dfs func(r, c, remain int)
	dfs = func(r, c, remain int) {
		if grid[r][c] == 2 {
			if remain == 1 {
				result++
			}
			return
		}

		temp := grid[r][c]
		grid[r][c] = -1

		// 枚举四个方向继续搜索
		for _, d := range dirs {
			nr := r + d[0]
			nc := c + d[1]
			if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
				continue
			}
			if grid[nr][nc] == -1 {
				continue
			}
			dfs(nr, nc, remain-1)
		}

		grid[r][c] = temp
	}

	dfs(startRow, startCol, total)
	return result
}

相似题目

题目	难度	考察点
62. 不同路径	中等	动态规划
63. 不同路径 II	中等	动态规划
79. 单词搜索	中等	回溯
1219. 黄金矿工	中等	回溯
980. 不同路径 III	困难	状态回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/18531579