vivo届秋季校招编程题

图中 找两点间的最短路径长度

广度搜索bfs/深度搜索dfs

vivo游戏中心的运营小伙伴最近接到一款新游戏的上架申请，为了保障用户体验，运营同学将按运营流程和规范对其做出分析评估。经过初步了解后分析得知，该游戏的地图可以用一个大小为 n*n 的矩阵表示，每个元素可以视为一个格子，根据游戏剧情设定其中某些格子是不可达的(比如建筑、高山、河流或者其它障碍物等)，现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径，以协助运营小伙伴评估该游戏的可玩性和上手难度。

输入描述:

第一行表示矩阵大小 n，5

第二行表示起点和终点的坐标

第三行起是一个用矩阵表示的游戏地图，其中#或者@表示障碍物，其他字母、非0数字、以及符号+、-、* 等等均表示普通可达格子，共有 n 行 n 列

输出描述:

输出最优路径的长度；若无法到达，则输出-1

DFS + 记忆数组

public class Main2 {private static int[][] next = {{0,1},{1,0},{0,-1},{-1,0}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();char[][] graph = new char[n][n];int s_y = sc.nextInt(),s_x = sc.nextInt(),e_y = sc.nextInt(),e_x = sc.nextInt();for(int i =0;i<n;i++){graph[i] = sc.next().toCharArray(); // 使用nextLine() 会把前面的回车读进去}int[][] mark = new int[n][n];dfs(s_x,s_y,graph,mark,e_x,e_y,1);System.out.println(mark[e_x][e_y]-1);}public static void dfs(int s_x, int s_y,char[][] graph, int[][] mark,int e_x,int e_y,int step){int n = mark.length;if(s_x<0 || s_x>=n || s_y<0 || s_y>=n || graph[s_x][s_y]=='#' || graph[s_x][s_y]=='@' || (mark[s_x][s_y]!=0 && mark[s_x][s_y]<=step)) return;mark[s_x][s_y] = step; // 记忆数组 记录当前位置的最短距离if (s_x == e_x && s_y == e_y) return;for(int i=0;i<next.length;i++){dfs(s_x+next[i][0],s_y+next[i][1],graph,mark,e_x,e_y,step+1);// 注意不要改变实参，仅改行参就够了 否则影响下一个分支的结果}}}

BFS

import javax.annotation.processing.SupportedSourceVersion;import java.util.*;import static java.lang.System.out;class Node{int x;int y;int step;public Node(int x, int y, int step) {this.x = x;this.y = y;this.step = step;}}public class Main2 {private static int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();char[][] graph = new char[n][n];int s_y = sc.nextInt(),s_x = sc.nextInt(),e_y = sc.nextInt(),e_x = sc.nextInt();for(int i =0;i<n;i++){graph[i] = sc.next().toCharArray(); // 使用nextLine() 会把前面的回车读进去// sc.next() 以空格分割}boolean[][] mark = new boolean[n][n];Queue<Node> q = new LinkedList<>();Node s = new Node(s_x,s_y,0);q.offer(s);mark[s.x][s.y] = true;while(!q.isEmpty()){Node cur = q.poll();if(cur.x == e_x && cur.y == e_y) {System.out.println(cur.step);return;}for(int i=0;i<next.length;i++){int x = cur.x + next[i][0];int y = cur.y + next[i][1];if(x>=0 && y>=0 && x<n && y<n && !mark[x][y] && graph[x][y]!='@' && graph[x][y]!='#') {q.offer(new Node(x, y, cur.step + 1)); // 把可以走的路 放到队列里mark[x][y] = true;}}}System.out.println(-1);return;}}

【vivo届秋季校招编程题】【java】广度优先搜索（BFS）/深度优先搜索（DFS）找最短路径长度