首页 > 试题广场 >

拜访

[编程题]拜访

热度指数：2851 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向或在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。

给定一个地图 CityMap 及它的行长度 n 和列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。

注意：需保证所有方案的距离都是最短的方案

数据范围： $2 \leq n,m \leq 10$

例如当输入为[[2,0,0,0],[0,-1,-1,0],[0,-1,1,0],[0,0,0,0]],4,4时，对应的4行4列CityMap如下图所示：

经理的位置在(2,2)，商家的位置在(0,0)，经分析，经理到达商家地址的最短方案有两种，分别为：

(2,2)->(2,3)->(1,3)->(0,3)->(0,2)->(0,1)->(0,0)

和

(2,2)->(3,2)->(3,1)->(3,0)->(2,0)->(1,0)->(0,0)，所以对应的返回值为2

示例1

输入

[[0,1,0],[2,0,0]],2,3

输出

示例2

输入

[[2,0,0,0],[0,-1,-1,0],[0,-1,1,0],[0,0,0,0]],4,4

输出

算法知识视频讲解

Java

pein531

深度优先搜索

解法有点暴力，但是很好理解。先遍历矩阵找到经理的位置，然后从该位置进行深搜，到达商家所在位置就对本次深搜的路径长度进行计数（用有序表来存储）。但其实我们没有必要统计长度很大的路径，因为最终我们只关心最短路径的方案数，那么我们根据业务，就可以分析得到如下4种情况停止深搜：

位置越界；
当前位置是不能走的区域；
当前路径的长度已经比之前记录的最小路径要长；
已经走过当前位置。

其余情况我们就继续探索4个方向，看哪个方向能继续走。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型二维数组 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    TreeMap<Integer, Integer> pathLenCounter = new TreeMap<>();
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    public int countPath (int[][] CityMap, int n, int m) {
        // write code here
        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);
                }
            }
        }
        return pathLenCounter.firstEntry().getValue();
    }
    
    private void dfs(int[][] grid, int x, int y, int steps, boolean[][] visited) {
        // 越界、不能走、遇到障碍物、已走过或路径变长，都停止本轮深搜
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1 || visited[x][y] || (!pathLenCounter.isEmpty() && steps > pathLenCounter.firstKey())){
            return;
        }
        if(grid[x][y] == 2){
            // 到达目的地，计算路径长度计数
            pathLenCounter.put(steps, pathLenCounter.getOrDefault(steps, 0) + 1);
        }else{
            visited[x][y] = true;
            for(int i = 0; i < 4; i++){
                dfs(grid, x + dx[i], y + dy[i], steps + 1, visited);
            }
            visited[x][y] = false;
        }
    }
}

发表于 2021-12-20 11:45:58 回复(0)

Python3

不想打工的海豚很快乐

bfs 每访问一个合法的位置时，如果之前访问过，并且现在访问的距离仍是之前访问的距离（bfs是最短的，因此这次访问只会大于等于上次访问的距离）那么将次数加当前点（即这个合法位置的父亲）以此方法访问过的次数visited

class Solution:
    def countPath(self , CityMap: List[List[int]], n: int, m: int) -> int:
        # write code here
        begin, target = [-1, -1], [-1, -1]
        m, n = len(CityMap), len(CityMap[0])
        for i in range(m):
            for j in range(n):
                if CityMap[i][j]==1: begin = [i, j]
                if CityMap[i][j]==2: target = [i, j]
        q = collections.deque()
        q.append(begin)
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        juli = 1
        key = False
        ans = 0
        visited = [[0]*n for _ in range(m)]
        visited[begin[0]][begin[1]] = 1
        while True:
            size = len(q)
            for _ in range(size):
                temp = q.popleft()
                for dir in dirs:
                    x, y = temp[0]+dir[0], temp[1]+dir[1]
                    if 0<=x<m and 0<=y<n:
                        if x==target[0] and y==target[1]:
                            key = True
                            ans += visited[temp[0]][temp[1]]
                            continue
                        elif [x, y]==begin: continue
                        if CityMap[x][y]==0:
                            visited[x][y] += visited[temp[0]][temp[1]]
                            CityMap[x][y] = juli
                            q.append([x, y])
                        elif CityMap[x][y]==juli:
                            visited[x][y] += visited[temp[0]][temp[1]]
            if not q&nbs***bsp;key: break
            juli += 1
        return ans

发表于 2023-09-22 22:27:28 回复(0)

C++

想回家的海螺在拧螺丝

#include <climits>
#include <vector>
class Solution {
  public:
    int minLen = INT_MAX; //记录最短路径

    int curLen = 0; //当前路径长度
    int ans = 0; //能到达最短路径的方案

    vector<vector<int>> dir{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    void dfs(int x, int y, vector<vector<int>>& CityMap) {
        int n = CityMap.size();
        int m = CityMap[0].size();

        //如果已经大于minLen了，直接返回
        if (curLen > minLen) {
            return;
        }
        //到达商家位置
        if (CityMap[x][y] == 1) {
            if (curLen < minLen) {
                minLen = curLen;
                ans = 1;
            } else if (curLen == minLen) {
                ans++;
            }
            return;
        }
        //标记visited
        CityMap[x][y] = 8;

        for (int i = 0; i < 4; i++) {
            int X = x + dir[i][0];
            int Y = y + dir[i][1];

            if (X < n && X >= 0 && Y < m && Y >= 0) {
                if (CityMap[X][Y] == 0 || CityMap[X][Y] == 1) {
                    curLen++;
                    dfs(X, Y, CityMap);
                    curLen--;
                }
            }
        }
        //回溯
        CityMap[x][y] = 0;
    }

    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //找到经理位置
                if (CityMap[i][j] == 2) {
                    dfs(i, j, CityMap);

                    return ans;
                }
            }
        }

        return ans;
    }
};

发表于 2023-05-06 14:12:20 回复(0)

Java

kelesong3

  public int countPath (int[][] map, int n, int m) {
    // write code here
    int step = 0;
    int[] dirs = {0,1,0,-1,0};
    // 找到起始坐标
    int ni = 0, nj = 0;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        if(map[i][j] == 1){
          ni = i;
          nj = j;
          break;
        }
      }
    }
    Queue<int[]> que = new LinkedList<>();
    que.offer(new int[]{ni, nj, 0});
    Map<Integer, Integer> mp = new HashMap<>();
    // 记录最短的路径key
    int min = Integer.MAX_VALUE;
    while(!que.isEmpty()){
      int size = que.size();
      // 走所有可能的下一步
      while(size-- > 0){
        int[] cur = que.poll();
        // 标记为走过了，防止死循环
        map[cur[0]][cur[1]] = -1;
        for(int i = 0; i < 4; i++){
          // 下一步的坐标
          int nx = cur[0] + dirs[i];
          int ny = cur[1] + dirs[i + 1];
          // 越界 || 已走过
          if(nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny] == -1) continue;
          if(map[nx][ny] == 2){
            // 到达目的地，最短路径数量 + 1
            mp.put(cur[2], mp.getOrDefault(cur[2], 0) + 1);
            // 更新最短路径最小key
            min = Math.min(min, cur[2]);
            continue;
          }
          // 下一步入队
          que.offer(new int[]{nx, ny, step});
        }
      }
      // 步数++
      step++;
    }
    return mp.get(min);
  }

发表于 2022-04-14 14:28:38 回复(0)

来自西班牙的橄榄树

package main

import (
   _"fmt"
)

func countPath(CityMap [][]int , n int , m int ) int {
    dir:=[4][2]int{
        {0,1},
        {0,-1},
        {1,0},
        {-1,0},
    }
    start :=[2]int{}
    for i:=0;i<len(CityMap);i++{
        for j:=0;j<len(CityMap[0]);j++{
            if CityMap[i][j]==1{
                start=[2]int{i,j}
            }
        }
    }

    dp:=make([][]int,n)
    dis:=make([][]int,n)
    vis:=make([][]bool,n)
    for i:=0;i<n;i++{
        dp[i]=make([]int,m)
        dis[i]=make([]int,m)
        vis[i]=make([]bool,m)
    }
    dp[start[0]][start[1]] =1
    dis[start[0]][start[1]] =1

    end:=[2]int{}
    flag:=false
    queue := [][2]int{start}
    for len(queue) >0{
        length := len(queue)
        for length > 0{
            x,y := queue[0][0],queue[0][1]
            queue=queue[1:]
            length--

            if CityMap[x][y]==2{
                end=[2]int{x,y}
                flag=true
                continue
            }

            for i := 0; i < 4; i++{
                u,v:=x+dir[i][0],y+dir[i][1]
                if u >= 0 && u < n && v >= 0 && v < m && CityMap[u][v] != -1 {
                    if vis[u][v]==false{
                        queue = append(queue,[2]int{u,v})
                        vis[u][v]=true
                        dis[u][v]=dis[x][y]+1
                        dp[u][v]=dp[x][y]
                    }else if dis[u][v]==dis[x][y]+1{
                        dp[u][v]+=dp[x][y]
                    }
                }
            }
        }
        if flag{
            return dp[end[0]][end[1]]
        }
    }
    return -1
}

发表于 2022-04-12 15:56:13 回复(0)

Python 3

Oliver1234

dfs + 回溯

可以直接在原图上将走过的点标记为1，就不用创建visited矩阵记录走过的位置，节省空间

用minlen记录当前最短路径的长度，res记录最短路径数量，一旦发现更短的路径，res重新从1开始计数，就不需要额外空间了

class Solution:
    def countPath(self , CityMap: List[List[int]], n: int, m: int) -> int:
        # write code here
        minlen, res = float('inf'), 0 # minlen记录当前最短路径长度，res记录最短路径数量
        def dfs(x,y,d): # dfs搜索，x，y为当前坐标，d为当前路径长度
            nonlocal minlen, res
            if d > minlen: return # 若当前路径>minlen，无需继续搜索
            if CityMap[x][y] == 2: # 若到达终点
                if d < minlen: # 当前路径比minlen短，则更新minlen，res重新开始计数
                    minlen = d
                    res = 1
                elif d == minlen: res += 1 # 如果路径长度=minlen，res++
                return
            else: # 未到达终点的情况
                CityMap[x][y] = 1 # 将当前位置标记为1，说明已走过
                for i, j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]: # 对于上下左右四个方向
                    if 0 <= i < n and 0 <=j < m and CityMap[i][j] != 1 and CityMap[i][j] != -1:
                        dfs(i,j,d+1) # 如果还在地图内且值不为1或-1，继续搜索
                CityMap[x][y] = 0 # 将当前点还原为0
        
        for i in range(n):
            for j in range(m):
                if CityMap[i][j] == 1: # 找到经理的位置并搜索
                    dfs(i,j,0)
        return res

发表于 2022-02-05 13:37:23 回复(0)