妈蛋！程序员的薪资已经跌破1万了。。

题目大概是这样子的：

题目描述：给定一个二维网格，网格中的每个单元格要么是0（表示空地），要么是1（表示障碍）。你从网格的左上角（起点）出发，目标是到达右下角（终点）。你只能向上、下、左、右四个方向移动，每次只能移动到相邻的空地上。请你判断是否可以到达终点。

要注意的地方：

• 如果起点或者终点被障碍物（即值为1）挡住，那么自然就不能到达了。
• 你可以使用广度优先搜索（BFS）或者深度优先搜索（DFS）来解决这个问题。

你可能会想，哎，这种题目是不是就做一个递归搜索，看看能不能从起点跳到终点？其实是可以的，但是有时候需要更高效的方法。接下来，我就来给大家讲讲怎么写。

解法：广度优先搜索（BFS）

这道题我最推荐使用广度优先搜索（BFS）。为什么？因为BFS是层层推进的，适合用来找最短路径或者判断是否可达。它可以让我们一层一层地探索网格，直到找到终点，或者发现没有可达的路径。

首先，BFS一般是通过队列来实现的。我们每次从队列中取出一个节点，检查它的四个方向，如果发现没有障碍物，就把它放入队列中，直到找到终点或者队列为空为止。

代码实现

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public boolean canReachEnd(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return false;
        }
        int m = grid.length;
        int n = grid[0].length;
        // 如果起点或终点被障碍物阻挡
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
            return false;
        }
        // 四个方向的移动
        int[] directions = {-1, 0, 1, 0, -1, 0};
                // 队列存储当前的位置
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        // 标记已访问的位置
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];
            // 如果到达终点
            if (x == m - 1 && y == n - 1) {
                return true;
            }
            // 探索四个方向
            for (int i = 0; i < 4; i++) {
                int newX = x + directions[i];
                int newY = y + directions[i + 1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY] && grid[newX][newY] == 0) {
                    queue.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }
        return false; // 队列为空，说明没有路径到达终点
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {
            {0, 0, 0, 1},
            {0, 1, 0, 0},
            {0, 0, 0, 0},
            {1, 0, 1, 0}
        };
        System.out.println(solution.canReachEnd(grid));  // 输出: true
    }
}

代码分析：

1. 队列（Queue）：我们使用一个队列来保存当前的节点坐标。每当从队列中取出一个节点时，我们会检查其四个方向的邻居。如果邻居是有效的（没有越界，也没有被障碍物阻挡），就将其加入队列。

2. visited 数组：为了避免重复访问同一个位置，我们用一个 visited 数组来标记每个位置是否已经访问过。

3. 四个方向的探索：我们通过 directions 数组来简化四个方向的探索。-1, 0, 1, 0, -1, 0 表示四个方向：上、右、下、左。

4. 终点判断：每次从队列中取出一个点时，我们检查它是否到达了终点（即右下角）。如果是，就返回 true。

复杂度分析：

• 时间复杂度：最坏情况下，我们需要遍历整个网格，时间复杂度是 O(m * n)，其中 m 和 n 分别是网格的行数和列数。

• 空间复杂度：由于我们需要一个 visited 数组来记录每个点是否被访问过，空间复杂度是 O(m * n)。

-END-

以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。