算法：迷宫问题

描述

定义一个二维数组 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≤n,m≤10  ， 输入的内容只包含  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)

说明：

注意：不能斜着走！！   

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint a = in.nextInt();int b = in.nextInt();int[][] array = new int[a][b];for (int i=0; i<a; i++) {for (int j=0; j<b; j++) {array[i][j] = in.nextInt();}}getRes1(array);}}public static void getRes1(int[][] array) {int dS = array.length;int rS = array[0].length;int[][] res = new int[dS][rS];Obj [][] objs = new Obj[dS][rS];Obj start = Obj.build(0, 0);start.before = null;objs[0][0] = start;// 消息队列Queue<Obj> queue = new LinkedList<>();queue.add(start);int[] chooses = {0, 1, 2, 3};while (!queue.isEmpty()) {Obj obj = queue.poll();// 已经存在数据的元素不允许被覆盖if (objs[obj.d][obj.r] == null) {objs[obj.d][obj.r] = obj.before;}if (obj.equals(dS-1, rS-1)) {break;}for (int i=0; i<chooses.length; i++) {switch(i) {case 0:if (obj.r+1<rS && array[obj.d][obj.r+1]==0) {Obj tmp = Obj.build(obj.d, obj.r+1);tmp.before = obj;queue.add(tmp);}break;case 1:if (obj.d+1<dS && array[obj.d+1][obj.r]==0) {Obj tmp = Obj.build(obj.d+1, obj.r);tmp.before = obj;queue.add(tmp);}break;case 2:if (obj.r-1>=0 && array[obj.d][obj.r-1]==0) {Obj tmp = Obj.build(obj.d, obj.r-1);tmp.before = obj;queue.add(tmp);}break;case 3:if (obj.d-1>=0 && array[obj.d-1][obj.r]==0) {Obj tmp = Obj.build(obj.d-1, obj.r);tmp.before = obj;queue.add(tmp);}break;}}}String s = "";if (objs[dS-1][rS-1] != null) {int i=dS-1, j=rS-1;s = "("+i+","+j+")\n";boolean bool = true;while (bool) {int d=objs[i][j].d;int r=objs[i][j].r;s = "("+d+","+r+")\n" + s;if ((d==0 && r==0)) {bool = false;}else {i = d;j = r;}}// s = "("+0+","+0+")\n"+s;System.out.println(s);}}public static class Obj {int d;int r;Obj before;public static Obj build(int d, int r) {Obj o = new Obj();o.d = d;o.r = r;return o;}public boolean equals(int d, int r) {return this.d==d && this.r==r;}}
}

 

            // 已经存在数据的元素不允许被覆盖，顺序应该是由下往上
            if (objs[obj.d][obj.r] == null) {
                objs[obj.d][obj.r] = obj.before;
            }