java题目 HJ43 迷宫问题

描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围： 2 \\le n,m \\le 10 \\2≤n,m≤10  ， 输入的内容只包含 0 \\le val \\le 1 \\0≤val≤1 

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

示例1

输入：

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

复制
输出：

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

复制

示例2

输入：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

复制
输出：

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

复制
说明：

注意：不能斜着走！！

 1 import java.io.*;
 2 import java.util.*;
 3 
 4 public class Main {
 5     public static void main(String[] args) throws IOException {
 6         Scanner sc = new Scanner(System.in);
 7         while(sc.hasNext()) {
 8             int n = sc.nextInt();
 9             int m = sc.nextInt();
10             //迷宫地图
11             int[][] map = new int[n][m];
12             for(int i =0;i<n;i++) {
13                 for(int j=0; j<m;j++) {
14                     map[i][j] = sc.nextInt();
15                 }
16             }
17             
18             //路径存储数组
19             List<Pos> path = new ArrayList<>();
20             //DFS搜索路径
21             dfs(map,0,0,path);
22             
23             //遍历路径每一步
24             for(Pos p : path) {
25                 System.out.println(\"(\" + p.x +\",\" + p.y +\")\");
26             }
27             
28         }
29     }
30      // 返回值 标记是否找到可通行的路劲
31     public static boolean dfs(int[][] map, int x, int y, List<Pos> path) {
32         //添加路径
33         path.add(new Pos(x, y));
34         map[x][y] = 1;
35         //结束标志
36         if(x ==map.length-1 && y == map[0].length -1) {
37             return true;
38         }
39         //向下能走时
40         if( x+1 < map.length && map[x+1][y] ==0 ) {
41             if(dfs(map, x+1, y, path)) {
42                 return true;
43             }
44         }
45         
46         //向右能走时
47         if( y+1 < map[0].length && map[x][y+1] ==0 ) {
48             if(dfs(map, x, y+1, path)) {
49                 return true;
50             }
51         }
52         
53         //向上能走时
54         if( x-1 > -1 && map[x-1][y] ==0 ) {
55             if(dfs(map, x-1, y, path)) {
56                 return true;
57             }
58         }
59         
60         //向左能走时
61         if( y-1 > -1 && map[x][y-1] ==0 ) {
62             if(dfs(map, x, y-1, path)) {
63                 return true;
64             }
65         }
66         //回溯
67         path.remove(path.size() -1);
68         return false;
69     }
70     
71     //坐标类
72     public static class Pos {
73     int x;
74     int y;
75     public Pos (int x, int y) {
76         this.x = x;
77         this.y = y;
78     }
79 }
80     
81 }

来源：https://www.cnblogs.com/m6233/p/15987638.html
本站部分图文来源于网络，如有侵权请联系删除。