一，走迷宮
1.題目描述：
給定一個?N×MN×M?的網格迷宮?GG。GG?的每個格子要么是道路，要么是障礙物（道路用?11?表示，障礙物用?00?表示）。
已知迷宮的入口位置為?(x1,y1)(x1?,y1?)，出口位置為?(x2,y2)(x2?,y2?)。問從入口走到出口，最少要走多少個格子。
2.實例：
輸入第?11?行包含兩個正整數?N,MN,M，分別表示迷宮的大小。
接下來輸入一個?N×MN×M?的矩陣。若?Gi,j=1Gi,j?=1?表示其為道路，否則表示其為障礙物。
最后一行輸入四個整數?x1,y1,x2,y2x1?,y1?,x2?,y2?，表示入口的位置和出口的位置。
1≤N,M≤1021≤N,M≤102，0≤Gi,j≤10≤Gi,j?≤1，1≤x1,x2≤N1≤x1?,x2?≤N，1≤y1,y2≤M1≤y1?,y2?≤M。
示例 1
輸入
5 5
1 0 1 1 0
1 1 0 1 1
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5
輸出
83.思路：
-
輸入處理：讀取輸入數據并轉換為迷宮矩陣。
-
坐標轉換：將入口和出口的位置轉換為從0開始的索引，方便數組操作。
-
障礙物檢查：直接檢查入口和出口是否為障礙物，如果是則立即返回-1。
-
BFS初始化：使用隊列來管理待處理的節點，距離數組記錄每個節點的最短步數。
-
BFS遍歷：從入口開始，逐層擴展遍歷所有可能的路徑，每次處理一個節點時檢查其四個方向，更新可達節點的距離并加入隊列。找到出口時立即輸出結果，否則遍歷結束后返回-1。
4：代碼：
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] maze = new int[n][m];// 讀取迷宮數據for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {maze[i][j] = scanner.nextInt();}}// 讀取起點和終點坐標并轉換為0-based索引int x1 = scanner.nextInt() - 1;int y1 = scanner.nextInt() - 1;int x2 = scanner.nextInt() - 1;int y2 = scanner.nextInt() - 1;// 檢查起點或終點是否為障礙物if (maze[x1][y1] == 0 || maze[x2][y2] == 0) {System.out.println(-1);return;}// 處理起點和終點相同的情況if (x1 == x2 && y1 == y2) {System.out.println(1);return;}// 初始化距離數組和隊列int[][] dist = new int[n][m];for (int[] row : dist) {Arrays.fill(row, -1);}dist[x1][y1] = 1;Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{x1, y1});// 四個方向移動的增量int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// BFS遍歷while (!queue.isEmpty()) {int[] current = queue.poll();int x = current[0];int y = current[1];for (int[] dir : directions) {int nx = x + dir[0];int ny = y + dir[1];// 檢查新坐標是否在迷宮范圍內if (nx >= 0 && nx < n && ny >= 0 && ny < m) {// 檢查是否是道路且未被訪問過if (maze[nx][ny] == 1 && dist[nx][ny] == -1) {dist[nx][ny] = dist[x][y] + 1;// 檢查是否到達終點if (nx == x2 && ny == y2) {System.out.println(dist[nx][ny]);return;}queue.add(new int[]{nx, ny});}}}}// 無法到達終點System.out.println(-1);}
}
