LeetCode 490. 迷宫

Categories:

题目描述
思路分析
1. 解法一：BFS（推荐）
相似题目

题目描述

✅ 490. 迷宫

思路分析

解法一：BFS（推荐）

核心思路：

球沿四个方向滚动，直到撞墙停下。

每次停下的位置视为新状态。

BFS 搜索能否到达终点。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示迷宫尺寸。

空间复杂度：O(m * n)，用于队列与访问标记。

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;

        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == destination[0] && cur[1] == destination[1]) {
                return true;
            }

            for (int k = 0; k < 4; k++) {
                int r = cur[0];
                int c = cur[1];
                while (r + dr[k] >= 0 && r + dr[k] < m && c + dc[k] >= 0 && c + dc[k] < n
                        && maze[r + dr[k]][c + dc[k]] == 0) {
                    r += dr[k];
                    c += dc[k];
                }

                if (!visited[r][c]) {
                    visited[r][c] = true;
                    queue.offer(new int[]{r, c});
                }
            }
        }

        return false;
    }
}

func hasPath(maze [][]int, start []int, destination []int) bool {
	m, n := len(maze), len(maze[0])
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}

	queue := make([][2]int, 0)
	queue = append(queue, [2]int{start[0], start[1]})
	visited[start[0]][start[1]] = true

	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		if cur[0] == destination[0] && cur[1] == destination[1] {
			return true
		}

		for _, d := range dirs {
			r, c := cur[0], cur[1]
			for r+d[0] >= 0 && r+d[0] < m && c+d[1] >= 0 && c+d[1] < n && maze[r+d[0]][c+d[1]] == 0 {
				r += d[0]
				c += d[1]
			}

			if !visited[r][c] {
				visited[r][c] = true
				queue = append(queue, [2]int{r, c})
			}
		}
	}

	return false
}

相似题目

题目	难度	考察点
505. 迷宫 II	中等	BFS
499. 迷宫 III	困难	BFS
1091. 二进制矩阵中的最短路径	中等	BFS
752. 打开转盘锁	中等	BFS
200. 岛屿数量	中等	BFS/DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/78897291