迷宮最短路徑【Java實作】

題目描述

現有一個

n∗m

大小的迷宮，其中

1

表示不可通過的牆壁， 表示平地。每次移動隻能向上下左右移動一格，且隻能移動到平地上。假設左上角坐标是

(1,1)

，行數增加的方向為

x

增長的方向，列數增加的方向為

y

增長的方向，求從迷宮左上角到右下角的最少步數的路徑。

輸入描述

第一行兩個整數

n、m（2≤n≤100,2≤m≤100）

，分别表示迷宮的行數和列數；

接下來

n

行，每行

m

個整數（值為 或

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<Pair> queue = new LinkedList<Pair>();
		// 廣度周遊時，(x,y)下标對應的上一個坐标
		Pair prePosition[][] = new Pair[n][m];
		Pair pair = new Pair(0, 0);
		prePosition[0][0] = new Pair(-1, -1);
		queue.addLast(pair);
		arr[0][0] = 1;
		int dx[] = { 0, 0, 1, -1 };
		int dy[] = { 1, -1, 0, 0 };
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Pair poll = queue.poll();
				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);
					for (int j = 0; j < 4; j++) {
						int nextX = poll.row + dx[j];
						int nextY = poll.cols + dy[j];
						if (canVisited(arr, n, m, nextX, nextY)) {
							queue.addLast(new Pair(nextX, nextY));
							prePosition[nextX][nextY] = pre;
							arr[nextX][nextY] = 1;
						}
					}
				}
			}
		}

	}

	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));
		}
	}

	public static boolean canVisited(int arr[][], int n, int m, int x, int y) {
		return x >= 0 && x < n && y >= 0 && y < m && arr[x][y] == 0;
	}

}

class Pair {
	int row;
	int cols;

	public Pair(int x, int y) {
		this.row = x;
		this.cols = y;
	}

}