华为机试-迷宫问题

题目描述 定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

int maze[5][5] = {

0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。 Input 一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。 Output 左上角到右下角的最短路径，格式如样例所示。 Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)

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

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

输入例子: 5 5 0 1 0 0 0 0 1 0 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)

---

代码

---

import java.util.Scanner; import java.util.Stack; public class Maze { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); while(sc.hasNext()) { int m=sc.nextInt(),n=sc.nextInt(); int a[][]=new int[m][n]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) { a[i][j]=sc.nextInt(); } leastRoute(m,n,a); } sc.close(); } public static void leastRoute(int m,int n,int a[][]) { Node start=new Node(0,0); Stack<Node> stack=new Stack<Node>(); stack.push(start); int[][] visited = new int[m][n];//标记是否被访问，这个要和Map大小对应 int[][] dir = {{1, 0}, {0, 1}};//定义两个方向横着走或者竖着走（题目中说只走这两个方向，当前也可以定义多个方向） while (!stack.isEmpty()) { boolean flag = false;//标记是否找了一个方向 Node pek = stack.peek();//获取栈顶元素，注意不需要出栈 if (pek.x == m-1 && pek.y == n-1) {//如果到达目的地则跳出循环 break; } else { for (int i = 0; i < 2; i++) {//循环两个方向 Node nbr = new Node(pek.x + dir[i][0], pek.y + dir[i][1]);//找到当前位置的邻居位置坐标并判断是否合法 if (nbr.x >= 0 && nbr.x < m && nbr.y >= 0 && nbr.y < n && a[nbr.x][nbr.y] == 0 && visited[nbr.x][nbr.y] == 0) {//判断邻居节点是否合法 stack.push(nbr);//合法将邻居位置加入栈 visited[nbr.x][nbr.y] = 1;//并标记该节点已经访问 flag = true;//找到了一个方向 break;//找到了就停止循环，顺着这个方向一直搜索 } } if (flag) {//找到了方向，就不用执行下面的出栈，沿着这个方向一直搜下去 continue; } stack.pop();//如果两个方向都不能通过，则出栈。 } } Stack<Node> stkRev = new Stack<Node>();//将路径反过来，因为栈中输出的路径是反的 while (!stack.isEmpty()) { stkRev.push(stack.pop()); } while (!stkRev.isEmpty()) { System.out.println("(" + stkRev.peek().x + "," + stkRev.peek().y + ")"); stkRev.pop(); } } } class Node { int x, y; public Node(int x, int y) { this.x = x; this.y = y; } }