题目描述

现有一个n∗m大小的迷宫，其中1表示不可通过的墙壁，0表示平地。每次移动只能向上下左右移动一格，且只能移动到平地上。假设左上角坐标是(1,1)，行数增加的方向为x增长的方向，列数增加的方向为y增长的方向，求从迷宫左上角到右下角的最少步数的路径。

输入描述

第一行两个整数n、m（2≤n≤100,2≤m≤100），分别表示迷宫的行数和列数；

接下来n行，每行m个整数（值为0或1），表示迷宫。

输出描述

从左上角的坐标开始，输出若干行（每行两个整数，表示一个坐标），直到右下角的坐标。

数据保证最少步数的路径存在且唯一。

样例

输入

3 3
0 1 0
0 0 0
0 1 0

输出

1 1
2 1
2 2
2 3
3 3

解释

假设左上角坐标是(1,1)，行数增加的方向为x增长的方向，列数增加的方向为y增长的方向。

可以得到从左上角到右下角的最少步数的路径为：(1,1)=>(2,1)=>(2,2)=>(2,3)=>(3,3)

思路分析

• 关于迷宫中最短路径的问题一般都采用广度优先搜索的思想，因为广度搜索“横扫千军”的形式确保了当前点到达其身边点时的距离一定是最小，以此类推，这样搜索下去到达目标点的距离也一定是最小的。
• 不过本题的难点是在于要求我们输出最短距离的具体路径，如果是深度优先搜索的话，使用递归就可以很好的输出路径，但是广度优先并不由递归的方式实现，因此如何确保到达目标位置后如何还能找到“回头路”（即怎么知道从那个点出发过来的）是我们要解决的问题。
• 一个好的办法是创建一个和地图同样维度的二维数组Pair prePosition[n][m]，其中Pair是我们的自定义类，其存放点的坐标信息，而在prePosition数组中则是存放到达当前点的上一个点的坐标信息，如prePosition[i][j]=new Pair(x,y)代表广度优先搜索中(x,y)的下一个点是(i,j)，初始(0,0)的上一个坐标是(-1,-1)。
• 我们通过普通的广度优先搜索从起点走向终点，在这一过程中注意记录当前点的上一个坐标，来到最后一个点时，只需要通过简单的递归就可以根据之前留下的“线索”定位到起始位置，接着进行打印即可。

代码实现

package homework;import java.util.LinkedList;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int arr[][] = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = scanner.nextInt();}}BFS(arr, n, m);}public static void BFS(int arr[][], int n, int m) {LinkedList queue = new LinkedList();// 广度遍历时，(x,y)下标对应的上一个坐标Pair prePosition[][] = new Pair[n][m];Pair pair = new Pair(0, 0);prePosition[0][0] = new Pair(-1, -1);queue.addLast(pair);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {Pair poll = queue.poll();arr[poll.row][poll.cols] = 1;if (poll.row == n - 1 && poll.cols == m - 1) {printCoord(prePosition, n - 1, m - 1);return;} else {Pair pre = new Pair(poll.row, poll.cols);if (poll.row - 1 >= 0 && arr[poll.row - 1][poll.cols] == 0) {queue.addLast(new Pair(poll.row - 1, poll.cols));prePosition[poll.row - 1][poll.cols] = pre;}if (poll.row + 1 < n && arr[poll.row + 1][poll.cols] == 0) {queue.addLast(new Pair(poll.row + 1, poll.cols));prePosition[poll.row + 1][poll.cols] = pre;}if (poll.cols + 1 < m && arr[poll.row][poll.cols + 1] == 0) {queue.addLast(new Pair(poll.row, poll.cols + 1));prePosition[poll.row][poll.cols + 1] = pre;}if (poll.cols - 1 >= 0 && arr[poll.row][poll.cols - 1] == 0) {queue.addLast(new Pair(poll.row, poll.cols - 1));prePosition[poll.row][poll.cols - 1] = pre;}}}}}static void printCoord(Pair prePosition[][], int row, int cols) {if (row != -1 && cols != -1) {Pair pair = prePosition[row][cols];printCoord(prePosition, pair.row, pair.cols);System.out.println((row + 1) + " " + (cols + 1));}}}class Pair {int row;int cols;public Pair(int x, int y) {this.row = x;this.cols = y;}}