描述

定义一个二维数组 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 }