2020京东917技术笔试-地图题（王子救公主）leecode-490

本文主要是介绍2020京东917技术笔试-地图题（王子救公主）leecode-490，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DFS

题目：王子在E，公主在S， .代表能走，#代表墙。问王子能找到公主吗？
（不知道王子找不找得到，反正我是凉了）
思路：地图转化成01态，然后就是leecode 490地图题了，居然还是付费的。

import java.util.Scanner;public class jingdong2 {public boolean hasPath(int[][] maze, int[] start, int[] destination) {boolean[][] visited = new boolean[maze.length][maze[0].length];return dfs(maze, start, destination, visited);}public boolean dfs(int[][] maze, int[] start, int[] destination, boolean[][] visited) {if (visited[start[0]][start[1]])return false;if (start[0] == destination[0] && start[1] == destination[1])return true;visited[start[0]][start[1]] = true;int r = start[1] + 1, l = start[1] - 1, u = start[0] - 1, d = start[0] + 1;while (r < maze[0].length && maze[start[0]][r] == 0) {// right//        System.out.println("go right! r="+r);r++;}if (dfs(maze, new int[] {start[0], r - 1}, destination, visited))return true;while (l >= 0 && maze[start[0]][l] == 0){//left//        System.out.println("go left! l="+l);l--;}if (dfs(maze, new int[] {start[0], l + 1}, destination, visited))return true;while (u >= 0 && maze[u][start[1]] == 0){//up//        System.out.println("go up! u="+u);u--;}if (dfs(maze, new int[] {u + 1, start[1]}, destination, visited))return true;while (d < maze.length && maze[d][start[1]] == 0){//down//       System.out.println("go down! d="+d);d++;}if (dfs(maze, new int[] {d - 1, start[1]}, destination, visited))return true;return false;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int st, n, m;int[] start = new int[2];int[] end = new int[2];int[][] map;st = Integer.valueOf(sc.nextLine());//场景数String[] str1 = sc.nextLine().split(" ");n = Integer.valueOf(str1[0]);//mapm = Integer.valueOf(str1[1]);map = new int[n][m];for (int se = 0; se < st; se++) {for (int i = 0; i < n; i++) {String temp = sc.nextLine();String[] temps = temp.split("");for (int j = 0; j < m; j++) {if (temps[j].equals(".")) {map[i][j] = 0;} else if (temps[j].equals("#")) {map[i][j] = 1;} else if (temps[j].equals("E")||temps[j].equals("e")) {map[i][j] = 0;start[0] = i;start[1] = j;} else if (temps[j].equals("S")||temps[j].equals("s")) {map[i][j] = 0;end[0] = i;end[1] = j;} else {System.out.println("WRONG INPUT!");}}}
//            System.out.println("start:"+start[0]+" "+start[1]);
//          System.out.println("end:"+end[0]+" "+end[1]);
//            for (int i = 0; i <n ; i++) {
//                for (int j = 0; j <m ; j++) {
//                    System.out.print(map[i][j]+" ");
//
//                }
//                System.out.println();
//            }System.out.println(new jingdong2().hasPath(map, start, end));}}}

这篇关于2020京东917技术笔试-地图题（王子救公主）leecode-490的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---