现在有一个城市销售经理,需要从公司出发,去拜访市内的某位 商家,已知他的位置以及商家的位置,但是由于城市道路交通的原因,他每次移动只能在左右中选择一个方向 或 在上下中选择一个方向,现在问他有多少种最短方案到达商家地址。 给定一个地图 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-笔试面试资料

这是qklbishe.com第19219 篇笔试面试资料
提供答案分析,通过本文《现在有一个城市销售经理,需要从公司出发,去拜访市内的某位 商家,已知他的位置以及商家的位置,但是由于城市道路交通的原因,他每次移动只能在左右中选择一个方向 或 在上下中选择一个方向,现在问他有多少种最短方案到达商家地址。 给定一个地图 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-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

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

给定一个地图 CityMap 及它的 行长度 n 和 列长度 m ,其中1代表经理位置, 2 代表商家位置, -1 代表不能经过的地区, 0 代表可以经过的地区,请返回方案数,保证一定存在合法路径。保证矩阵的长宽都小于等于 10。
注意:需保证所有方案的距离都是最短的方案
数据范围:现在有一个城市销售经理,需要从公司出发,去拜访市内的某位 商家,已知他的位置以及商家的位置,但是由于城市道路交通的原因,他每次移动只能在左右中选择一个方向  或 在上下中选择一个方向,现在问他有多少种最短方案到达商家地址。    给定一个地图 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
例如当输入为[[2,0,0,0],[0,-1,-1,0],[0,-1,1,0],[0,0,0,0]],4,4时,对应的4行4列CityMap如下图所示:
现在有一个城市销售经理,需要从公司出发,去拜访市内的某位 商家,已知他的位置以及商家的位置,但是由于城市道路交通的原因,他每次移动只能在左右中选择一个方向  或 在上下中选择一个方向,现在问他有多少种最短方案到达商家地址。    给定一个地图 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
经理的位置在(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
Java

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

深度优先搜索

解法有点暴力,但是很好理解。先遍历矩阵找到经理的位置,然后从该位置进行深搜,到达商家所在位置就对本次深搜的路径长度进行计数(用有序表来存储)。但其实我们没有必要统计长度很大的路径,因为最终我们只关心最短路径的方案数,那么我们根据业务,就可以分析得到如下4种情况停止深搜:
  1. 位置越界;
  2. 当前位置是不能走的区域;
  3. 当前路径的长度已经比之前记录的最小路径要长;
  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;         }     } }

今天 11:45:58 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 现在有一个城市销售经理,需要从公司出发,去拜访市内的某位 商家,已知他的位置以及商家的位置,但是由于城市道路交通的原因,他每次移动只能在左右中选择一个方向 或 在上下中选择一个方向,现在问他有多少种最短方案到达商家地址。 给定一个地图 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-笔试面试资料

提供最优质的资源集合

立即查看 了解详情