#yyds干货盘点# 名企真题专题：拜访

1.简述：

描述

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

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

输入：

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

返回值：

2

2.代码实现：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型二维数组 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int[][] directions = new int[][]{{1,0}, {-1, 0}, {0,1}, {0, -1}};
    public int countPath (int[][] CityMap, int n, int m) {
        // write code here
        int ans = 0;
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(CityMap[i][j]==1){  //找到起点
                    queue.offer(new int[]{i,j});
                }
            }
        }
        while(!queue.isEmpty()){
            for(int i=queue.size(); i>0; i--){  //层次遍历
                int[] p = queue.poll();
                int x = p[0], y = p[1];
                if(CityMap[x][y]==2){
                    ans++;
                    continue;
                }
                CityMap[x][y] = -1;  //代表本层已访问
                for(int[] direction : directions){
                    int newx = x + direction[0];
                    int newy = y + direction[1];
                    if(newx>=n || newx<0 || newy<0 || newy>=m || CityMap[newx][newy]==-1){  //排除不可达
                        continue;
                    }else{
                        queue.offer(new int[]{newx, newy});
                    }
                }
            }
            if(ans!=0){
                break;
            }
        }
        return ans;
    }
}