题解 | 迷宫寻路

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int n, m;
    static char[][] maze;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        m = in.nextInt();
        maze = new char[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            maze[i] = in.next().toCharArray();
        }

        // System.out.println(dfs(0, 0) ? "Yes" : "No");
        System.out.println(bfs(0, 0) ? "Yes" : "No");
    }

    // 深度优先搜索
    private static boolean dfs(int x, int y) {
        // 到达终点
        if (x == n - 1 && y == m - 1) return true;
		// 标记当前格子是否已经走过
        visited[x][y] = true;
		// 尝试4个方向：利用方向数组
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 边界检查、墙体检查、访问检查
            if(nx >= 0 && nx < n && ny >= 0 && ny < m
            && maze[nx][ny] == '.' && !visited[nx][ny]) {
                if(dfs(nx, ny)) return true;
            }
        }

        return false;
    }

    // 广度优先搜索
    private static boolean bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
	  	// 初始化队列：添加起点
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

        boolean found = false;
	  	// 循环处理：只要队列里还有“待探索”的格子，就继续
        while(!queue.isEmpty()) {
		  	// 出队：拿出当前最先发现的格子
            int[] curr = queue.poll();
		  	// 到达终点
            if(curr[0] == n - 1 && curr[1] == m - 1) {
                found = true;
                break;
            }
			// 扩散：检查四周
            for(int i = 0; i < 4; i++) {
                int nx = curr[0] + dx[i];
                int ny = curr[1] + dy[i];

                if(nx >= 0 && nx < n && ny >= 0 && ny < m
                && maze[nx][ny] == '.' && !visited[nx][ny]) {
				  	// 入队并标记：把这个新发现的空地加入队列，并立刻标记为已访问
				  	// 注意：BFS 中要在入队时标记，否则同一个点可能被多次加入队列
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }

        return found;
    }
}