解题思路

这是一道使用DFS求最短路径方案数的问题，主要思路如下：

  1. 问题分析：

    • 在 的网格中寻找从经理(1)到商家(2)的最短路径
    • 需要统计最短路径的方案数
    • 有障碍物(-1)不能通过

  2. 解决方案：

    • 使用 DFS 遍历所有可能的路径
    • 使用 map 存储不同路径长度对应的方案数
    • 剪枝优化：长于当前最短路径的分支直接返回

  3. 关键点：

    • 使用 visited 数组避免重复访问
    • 四个方向的移动使用方向数组
    • 回溯时恢复 visited 状态

代码

class Solution {
private:
    // 存储(路径长度，方案数)映射
    map<int, int> pathCount;
    // 方向数组：右、下、上、左
    int dx[4] = {0, 1, -1, 0};
    int dy[4] = {1, 0, 0, -1};
    
    void dfs(vector<vector<int>>& grid, int x, int y, int dist, 
            vector<vector<int>>& visited, int n, int m) {
        // 边界检查
        if (x < 0 || x >= n || y < 0 || y >= m) return;
        
        // 剪枝条件：障碍物、已访问、路径过长
        if (grid[x][y] == -1 || visited[x][y] || 
            (!pathCount.empty() && dist > pathCount.begin()->first)) {
            return;
        }
        
        // 到达商家，记录方案
        if (grid[x][y] == 2) {
            pathCount[dist]++;
            return;
        }
        
        // 标记访问并继续搜索
        visited[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            dfs(grid, x + dx[i], y + dy[i], dist + 1, visited, n, m);
        }
        // 回溯，取消标记
        visited[x][y] = 0;
    }
    
public:
    int countPath(vector<vector<int>>& CityMap, int n, int m) {
        vector<vector<int>> visited(n, vector<int>(m, 0));
        
        // 找到经理位置并开始搜索
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (CityMap[i][j] == 1) {
                    dfs(CityMap, i, j, 0, visited, n, m);
                }
            }
        }
        
        return pathCount.empty() ? 0 : pathCount.begin()->second;
    }
};

import java.util.*;

class Solution {
    // 存储(路径长度，方案数)映射
    private TreeMap<Integer, Integer> pathCount = new TreeMap<>();
    // 方向数组：右、下、上、左
    private int[] dx = {0, 1, -1, 0};
    private int[] dy = {1, 0, 0, -1};
    
    private void dfs(int[][] grid, int x, int y, int dist, 
                    boolean[][] visited, int n, int m) {
        // 边界检查
        if (x < 0 || x >= n || y < 0 || y >= m) return;
        
        // 剪枝条件：障碍物、已访问、路径过长
        if (grid[x][y] == -1 || visited[x][y] || 
            (!pathCount.isEmpty() && dist > pathCount.firstKey())) {
            return;
        }
        
        // 到达商家，记录方案
        if (grid[x][y] == 2) {
            pathCount.put(dist, pathCount.getOrDefault(dist, 0) + 1);
            return;
        }
        
        // 标记访问并继续搜索
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            dfs(grid, x + dx[i], y + dy[i], dist + 1, visited, n, m);
        }
        // 回溯，取消标记
        visited[x][y] = false;
    }
    
    public int countPath(int[][] CityMap, int n, int m) {
        boolean[][] visited = new boolean[n][m];
        
        // 找到经理位置并开始搜索
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (CityMap[i][j] == 1) {
                    dfs(CityMap, i, j, 0, visited, n, m);
                }
            }
        }
        
        return pathCount.isEmpty() ? 0 : pathCount.firstEntry().getValue();
    }
}

from collections import defaultdict

class Solution:
    def countPath(self, CityMap: List[List[int]], n: int, m: int) -> int:
        # 存储(路径长度，方案数)映射
        path_count = defaultdict(int)
        # 方向数组：右、下、上、左
        dx = [0, 1, -1, 0]
        dy = [1, 0, 0, -1]
        visited = [[False] * m for _ in range(n)]
        
        def dfs(x: int, y: int, dist: int) -> None:
            # 边界检查
            if x < 0 or x >= n or y < 0 or y >= m:
                return
                
            # 剪枝条件：障碍物、已访问、路径过长
            if (CityMap[x][y] == -1 or visited[x][y] or 
                (path_count and dist > min(path_count.keys()))):
                return
                
            # 到达商家，记录方案
            if CityMap[x][y] == 2:
                path_count[dist] += 1
                return
                
            # 标记访问并继续搜索
            visited[x][y] = True
            for i in range(4):
                dfs(x + dx[i], y + dy[i], dist + 1)
            # 回溯，取消标记
            visited[x][y] = False
        
        # 找到经理位置并开始搜索
        for i in range(n):
            for j in range(m):
                if CityMap[i][j] == 1:
                    dfs(i, j, 0)
        
        return path_count[min(path_count.keys())] if path_count else 0

算法及复杂度

  • 算法：深度优先搜索(DFS) + 回溯
  • 时间复杂度： - 最坏情况下需要遍历所有可能的路径
  • 空间复杂度： - 需要 visited 数组和递归栈空间