【双机位A卷】华为OD笔试之【DFS/BFS】双机位A-陷阱方格【Py/Java/C++/C/JS/Go六种语言OD独家双机位A卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

942人浏览 · 2025-09-19 16:07:53

闭着眼睛学算法 · 2025-09-19 16:07:53 发布

可上欧弟OJ系统练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

题目描述与示例

题目描述

房间由X*Y的方格组成，例如下图为6*4的大小。每一个方格以坐标(x, y)描述。
机器人固定从方格(0, 0)出发，只能向东或者向北前进。出口固定为房间的最东北角，如下图的方格(5, 3)。用例保证机器人可以从入口走到出口。
房间有些方格是墙壁，如(4，1)，机器人不能经过那儿。
有些地方是一旦到达就无法走到出口的，如标记为B的方格，称之为陷阱方格。
有些地方是机器人无法到达的，如标记为A的方格，称之为不可达方格，不可达方格不包括墙壁所在的位置。
如下示例图中，陷阱方格有2个，不可达方格有3个。
请为该机器人实现路径规划功能：给定房间大小、墙壁位置，请计算出陷阱方格与不可达方格分别有多少个。

在这里插入图片描述

输入描述

第一行为房间的X和Y (0`` ``<`` ``X，Y <= 1000)

第二行为房间中墙壁的个数N (0 <= N <`` ``X*Y)

接着下面会有N行墙壁的坐标

输出描述

陷阱方格与不可达方格数量，两个信息在一行中输出,以一个空格隔开。(结尾不带回车换行)

示例一

输入

输出

2 3

示例二

输入

输出

6 4

说明

在这里插入图片描述

解题思路

本题是一道非常有意思的题目，显然路径的搜索过程可以用DFS/BFS来完成。问题在于如何判断方格是不可达方格和陷阱方格。

不可达方格的判断

先考虑相对直观的不可达方格的判断。

我们从起点到终点进行DFS/BFS（注意搜索方向只有向上或向右两个方向），将能够到达的方格在检查数组check_list1中标记为True。搜索完成后，check_list1中所有不为墙壁的False数量，即为不可达方格的数量。

unreachable_num = sum(1 if check_list1[x][y] == False else 0
               for y in range(m) for x in range(n))

在这里插入图片描述

显然上述做法只能够算出不可达方格的数量，因为陷阱方格在搜索过程中是可以到达的。

逆向路径的概念

在判断陷阱方格之前，需要构建一个逆向路径的概念。

如果从某个点(i, j)出发（这个点不一定是起点），只历经向右和向上最终到达终点，那么相对应的，从终点出发也可以只历经向左和向下最终到达该点(i, j)，这条路径我们称之为原路径的逆向路径。

在这里插入图片描述

很容易证明，如果某条路径存在，那么其逆向路径也一定存在。

在这里插入图片描述

陷阱方格的判断

陷阱方格的判断需要借助逆向路径的概念来完成。假设一个方格(i, j)是陷阱方格，它应该满足以下两个要求：

从起点出发，能够到达(i, j)。即从(0, 0)到(i, j)的路径存在。
从(i, j)出发，不能够到达终点(n-1, m-1)。即从(i, j)出发到终点(n-1, m-1)的路径不存在。

上述第一个条件其实非常容易满足。在不可达方格判断中，check_list1中标记为True的点，就是从起点出发能够到达的点。

对于上述的第二个条件，我们可以用逆向路径的概念来描述：

从终点(n-1, m-1)出发到点(i, j)的逆向路径不存在。

因此对于第二个条件，我们可以从终点到起点进行逆向路径的DFS/BFS（注意搜索方向只有向左或向下两个方向），能够到达的位置在检查数组check_list2中标记为True。搜索完成后，check_list2中所有不为墙壁的值为False的点，即为从终点出发的逆向路径无法到达的点。

在这里插入图片描述

在check_list1中值为True，在check_list2中值为False的点（且不为墙壁），即是满足上述两个条件的点，也就是陷阱方格。统计满足条件的方格数量即可。

trap_num = sum(1 if (check_list2[x][y] == False and check_list1[x][y] == True) else 0
               for y in range(m) for x in range(n))

其他特殊处理

至此，本题的分析已经大体完成，我们需要做两次DFS/BFS搜索

第一次从起点出发往终点搜寻，方向只有向上和向右
第二次从终点出发往起点搜寻，方向只有向下和向左

不管是BFS过程还是DFS过程，和常规的搜索过程无异。

另外，考虑到在计算checkList中值的时候需要排除掉墙壁，我们可以在墙壁的初始化时，就把checkList1和checkList2中墙壁所对应的点标记为True，这样可以免去最后一步计数时的繁琐判断。

代码

解法一：BFS

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2023B/2025B-陷阱方格
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问


from collections import deque

# 输入网格的长、宽
n, m = map(int, input().split())
# 构建地图
grid = [[0] * m for _ in range(n)]

# 构建两个检查数组，分别用于正向搜寻和逆向搜寻
check_list1 = [[False] * m for _ in range(n)]
check_list2 = [[False] * m for _ in range(n)]

# 输入墙壁方格的数量
wall_num = int(input())
for _ in range(wall_num):
    # 输入墙壁坐标
    x, y = map(int, input().split())
    # 将点(x,y)在grid中设置为1，表示是墙壁
    grid[x][y] = 1
    # 并且在check_list中标记为True
    check_list1[x][y] = True
    check_list2[x][y] = True


# 第一次BFS：从起点往终点进行
q = deque()
q.append((0, 0))
# 起点标记为已检查过
check_list1[0][0] = True
# 进行BFS
# 注意第一次BFS所用的检查数组是check_list1
while len(q) > 0:
    # 弹出队头元素(x, y)，为当前点
    x, y = q.popleft()
    # 从起点往终点的路径，只能向上或者向右
    # 故当前点(x, y)的近邻点，只有(x, y+1)和(x+1, y)两个点
    for nx, ny in [(x, y+1), (x+1, y)]:
        # 判断越界时，只需要考虑上边界即可
        if nx < n and ny < m and check_list1[nx][ny] == False and grid[nx][ny] == 0:
            # 将近邻点(nx, ny)加入队列，同时修改为已检查
            q.append((nx, ny))
            check_list1[nx][ny] = True


# 退出BFS搜索后，check_list1中尚未搜寻过的点，即为【不可达方格】
# 计算check_list1中值为False的数目，即为【不可达方格】的数目
unreachable_num = sum(1 if check_list1[x][y] == False else 0
               for y in range(m) for x in range(n))

# 第二次BFS：从终点往起点进行
q = deque()
q.append((n-1, m-1))
# 终点标记为已检查过
check_list2[n-1][m-1] = True
# 进行BFS
# 注意第二次BFS所用的检查数组是check_list2
while len(q) > 0:
    # 弹出队头元素(x, y)，为当前点
    x, y = q.popleft()
    # 从终点往起点的路径，只能向下或者向向左
    # 故当前点(x, y)的近邻点，只有(x, y-1)和(x-1, y)两个点
    for nx, ny in [(x, y-1), (x-1, y)]:
        # 判断越界时，只需要考虑下边界即可
        if nx >= 0 and ny >= 0 and check_list2[nx][ny] == False and grid[nx][ny] == 0:
            # 将近邻点(nx, ny)加入队列，同时修改为已检查
            q.append((nx, ny))
            check_list2[nx][ny] = True

# 退出BFS搜索后，check_list2中尚未搜寻过且在check_list1中搜索寻过的点，即为【陷阱方格】
# 计算check_list2中值为False且在check_list1中值为True的数目，即为【陷阱方格】的数目
trap_num = sum(1 if (check_list2[x][y] == False and check_list1[x][y] == True) else 0
               for y in range(m) for x in range(n))


# 分别输出【陷阱方格】和【不可达方格】的数目，用空格隔开即为答案
print("{} {}".format(trap_num, unreachable_num))

Java

import java.util.ArrayDeque;
import java.util.Queue;
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[][] grid = new int[n][m];
        boolean[][] checkList1 = new boolean[n][m];
        boolean[][] checkList2 = new boolean[n][m];

        int wallNum = scanner.nextInt();
        for (int i = 0; i < wallNum; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            grid[x][y] = 1;
            checkList1[x][y] = true;
            checkList2[x][y] = true;
        }

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0});
        checkList1[0][0] = true;

        while (!queue.isEmpty()) {
            int[] coords = queue.poll();
            int x = coords[0];
            int y = coords[1];

            int[][] moves = {{x, y + 1}, {x + 1, y}};
            for (int[] move : moves) {
                int nx = move[0];
                int ny = move[1];
                if (nx < n && ny < m && !checkList1[nx][ny] && grid[nx][ny] == 0) {
                    queue.add(new int[]{nx, ny});
                    checkList1[nx][ny] = true;
                }
            }
        }

        int unreachableNum = 0;
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (!checkList1[x][y]) {
                    unreachableNum++;
                }
            }
        }

        queue.add(new int[]{n - 1, m - 1});
        checkList2[n - 1][m - 1] = true;

        while (!queue.isEmpty()) {
            int[] coords = queue.poll();
            int x = coords[0];
            int y = coords[1];

            int[][] moves = {{x, y - 1}, {x - 1, y}};
            for (int[] move : moves) {
                int nx = move[0];
                int ny = move[1];
                if (nx >= 0 && ny >= 0 && !checkList2[nx][ny] && grid[nx][ny] == 0) {
                    queue.add(new int[]{nx, ny});
                    checkList2[nx][ny] = true;
                }
            }
        }

        int trapNum = 0;
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (!checkList2[x][y] && checkList1[x][y]) {
                    trapNum++;
                }
            }
        }

        System.out.println(trapNum + " " + unreachableNum);
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> check_list1(n, vector<bool>(m, false));
    vector<vector<bool>> check_list2(n, vector<bool>(m, false));

    int wall_num;
    cin >> wall_num;
    for (int i = 0; i < wall_num; i++) {
        int x, y;
        cin >> x >> y;
        grid[x][y] = 1;
        check_list1[x][y] = true;
        check_list2[x][y] = true;
    }

    queue<pair<int, int>> q;
    q.push({0, 0});
    check_list1[0][0] = true;

    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        for (auto [nx, ny] : vector<pair<int, int>>{{x, y + 1}, {x + 1, y}}) {
            if (nx < n && ny < m && !check_list1[nx][ny] && grid[nx][ny] == 0) {
                q.push({nx, ny});
                check_list1[nx][ny] = true;
            }
        }
    }

    int unreachable_num = 0;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if (!check_list1[x][y]) {
                unreachable_num++;
            }
        }
    }

    q.push({n - 1, m - 1});
    check_list2[n - 1][m - 1] = true;

    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        for (auto [nx, ny] : vector<pair<int, int>>{{x, y - 1}, {x - 1, y}}) {
            if (nx >= 0 && ny >= 0 && !check_list2[nx][ny] && grid[nx][ny] == 0) {
                q.push({nx, ny});
                check_list2[nx][ny] = true;
            }
        }
    }

    int trap_num = 0;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if (!check_list2[x][y] && check_list1[x][y]) {
                trap_num++;
            }
        }
    }

    cout << trap_num << " " << unreachable_num << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdbool.h>

#define MAXN 1005   /* 视测试数据规模自行修改 */
#define MAXM 1005

/* 简单循环队列存储坐标 (x, y) */
typedef struct {
    int x, y;
} Node;

typedef struct {
    Node data[MAXN * MAXM];
    int front, rear;
} Queue;

/* 初始化队列 */
void initQueue(Queue *q) { q->front = q->rear = 0; }

/* 入队 */
void push(Queue *q, int x, int y) {
    q->data[q->rear].x = x;
    q->data[q->rear].y = y;
    q->rear++;
}

/* 出队 */
Node pop(Queue *q) { return q->data[q->front++]; }

/* 判空 */
bool empty(Queue *q) { return q->front == q->rear; }

int main(void) {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;

    /* 地图：0 表示空地，1 表示墙 */
    static int grid[MAXN][MAXM] = {0};
    static bool vis1[MAXN][MAXM] = {0};   /* 从 (0,0) 正向可达 */
    static bool vis2[MAXN][MAXM] = {0};   /* 从 (n-1,m-1) 逆向可达 */

    int wall_num;
    scanf("%d", &wall_num);
    while (wall_num--) {
        int x, y;
        scanf("%d %d", &x, &y);
        grid[x][y] = 1;
        vis1[x][y] = vis2[x][y] = true;   /* 提前标记墙为已访问，便于后续判断 */
    }

    /************  第一次 BFS：只能向右 / 向下  ************************/
    Queue q1;
    initQueue(&q1);
    push(&q1, 0, 0);
    vis1[0][0] = true;

    const int dx1[2] = {0, 1};   /* 右、下 */
    const int dy1[2] = {1, 0};

    while (!empty(&q1)) {
        Node cur = pop(&q1);
        for (int k = 0; k < 2; ++k) {
            int nx = cur.x + dx1[k];
            int ny = cur.y + dy1[k];
            if (nx < n && ny < m && !vis1[nx][ny] && grid[nx][ny] == 0) {
                vis1[nx][ny] = true;
                push(&q1, nx, ny);
            }
        }
    }

    int unreachable = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (!vis1[i][j]) ++unreachable;

    /************  第二次 BFS：只能向左 / 向上  ************************/
    Queue q2;
    initQueue(&q2);
    push(&q2, n - 1, m - 1);
    vis2[n - 1][m - 1] = true;

    const int dx2[2] = {0, -1};  /* 左、上 */
    const int dy2[2] = {-1, 0};

    while (!empty(&q2)) {
        Node cur = pop(&q2);
        for (int k = 0; k < 2; ++k) {
            int nx = cur.x + dx2[k];
            int ny = cur.y + dy2[k];
            if (nx >= 0 && ny >= 0 && !vis2[nx][ny] && grid[nx][ny] == 0) {
                vis2[nx][ny] = true;
                push(&q2, nx, ny);
            }
        }
    }

    int trap = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            /* 正向可达且逆向不可达的空地为“陷阱” */
            if (vis1[i][j] && !vis2[i][j]) ++trap;

    printf("%d %d\n", trap, unreachable);
    return 0;
}

Node JavaScript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
rl.on("line", line => {
    inputLines.push(line.trim());
});

rl.on("close", () => {
    // 读取输入的基本信息
    const [n, m] = inputLines[0].split(' ').map(Number);
    const grid = Array.from({ length: n }, () => Array(m).fill(0));
    const checkList1 = Array.from({ length: n }, () => Array(m).fill(false));
    const checkList2 = Array.from({ length: n }, () => Array(m).fill(false));

    const wallNum = parseInt(inputLines[1]);
    for (let i = 0; i < wallNum; i++) {
        const [x, y] = inputLines[2 + i].split(' ').map(Number);
        grid[x][y] = 1;
        checkList1[x][y] = true;
        checkList2[x][y] = true;
    }

    // 从左上角开始BFS，只能向右或向下
    let queue = [[0, 0]];
    checkList1[0][0] = true;

    while (queue.length > 0) {
        const [x, y] = queue.shift();
        const moves = [[x + 1, y], [x, y + 1]];
        for (const [nx, ny] of moves) {
            if (nx < n && ny < m && !checkList1[nx][ny] && grid[nx][ny] === 0) {
                queue.push([nx, ny]);
                checkList1[nx][ny] = true;
            }
        }
    }

    // 统计无法从左上角到达的点数
    let unreachableNum = 0;
    for (let x = 0; x < n; x++) {
        for (let y = 0; y < m; y++) {
            if (!checkList1[x][y]) {
                unreachableNum++;
            }
        }
    }

    // 从右下角开始BFS，只能向左或向上
    queue = [[n - 1, m - 1]];
    checkList2[n - 1][m - 1] = true;

    while (queue.length > 0) {
        const [x, y] = queue.shift();
        const moves = [[x - 1, y], [x, y - 1]];
        for (const [nx, ny] of moves) {
            if (nx >= 0 && ny >= 0 && !checkList2[nx][ny] && grid[nx][ny] === 0) {
                queue.push([nx, ny]);
                checkList2[nx][ny] = true;
            }
        }
    }

    // 统计陷阱点数（能从起点到达但无法到终点）
    let trapNum = 0;
    for (let x = 0; x < n; x++) {
        for (let y = 0; y < m; y++) {
            if (checkList1[x][y] && !checkList2[x][y]) {
                trapNum++;
            }
        }
    }

    // 输出结果
    console.log(`${trapNum} ${unreachableNum}`);
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

// 创建队列结构用于BFS
type Queue [][]int

func (q *Queue) Enqueue(item []int) {
        *q = append(*q, item)
}

func (q *Queue) Dequeue() []int {
        item := (*q)[0]
        *q = (*q)[1:]
        return item
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)
        input := []string{}
        for scanner.Scan() {
                line := strings.TrimSpace(scanner.Text())
                if line != "" {
                        input = append(input, line)
                }
        }

        nm := strings.Fields(input[0])
        n, _ := strconv.Atoi(nm[0])
        m, _ := strconv.Atoi(nm[1])

        grid := make([][]int, n)
        checkList1 := make([][]bool, n)
        checkList2 := make([][]bool, n)
        for i := range grid {
                grid[i] = make([]int, m)
                checkList1[i] = make([]bool, m)
                checkList2[i] = make([]bool, m)
        }

        wallNum, _ := strconv.Atoi(input[1])
        for i := 0; i < wallNum; i++ {
                pos := strings.Fields(input[2+i])
                x, _ := strconv.Atoi(pos[0])
                y, _ := strconv.Atoi(pos[1])
                grid[x][y] = 1
                checkList1[x][y] = true
                checkList2[x][y] = true
        }

        queue := Queue{{0, 0}}
        checkList1[0][0] = true
        dx1 := []int{0, 1}
        dy1 := []int{1, 0}

        for len(queue) > 0 {
                cur := queue.Dequeue()
                x, y := cur[0], cur[1]
                for i := 0; i < 2; i++ {
                        nx, ny := x+dx1[i], y+dy1[i]
                        if nx < n && ny < m && !checkList1[nx][ny] && grid[nx][ny] == 0 {
                                queue.Enqueue([]int{nx, ny})
                                checkList1[nx][ny] = true
                        }
                }
        }

        unreachableNum := 0
        for x := 0; x < n; x++ {
                for y := 0; y < m; y++ {
                        if !checkList1[x][y] {
                                unreachableNum++
                        }
                }
        }

        queue = Queue{{n - 1, m - 1}}
        checkList2[n-1][m-1] = true
        dx2 := []int{0, -1}
        dy2 := []int{-1, 0}

        for len(queue) > 0 {
                cur := queue.Dequeue()
                x, y := cur[0], cur[1]
                for i := 0; i < 2; i++ {
                        nx, ny := x+dx2[i], y+dy2[i]
                        if nx >= 0 && ny >= 0 && !checkList2[nx][ny] && grid[nx][ny] == 0 {
                                queue.Enqueue([]int{nx, ny})
                                checkList2[nx][ny] = true
                        }
                }
        }

        trapNum := 0
        for x := 0; x < n; x++ {
                for y := 0; y < m; y++ {
                        if checkList1[x][y] && !checkList2[x][y] {
                                trapNum++
                        }
                }
        }

        fmt.Printf("%d %d\n", trapNum, unreachableNum)
}

解法二：DFS

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2023B/2025B/双机位A-陷阱方格
# 分值：200
# 作者：大厂训练营第一期学员-海绵
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问

import sys
sys.setrecursionlimit(1000000)    # 这里不一定设置1000000，设置成一个很大的数即可
 
def DFS1(grid, check_list1, x, y):
    check_list1[x][y] = True
    # 从起点到终点，只能上右
    for dx, dy in [(0,1), (1,0)]:
        nx, ny = x+dx, y+dy
        # 如果不越界，且不为墙壁，且未被检查过
        if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 0 and check_list1[nx][ny] == False:
            # 执行DFS
            DFS1(grid, check_list1, nx, ny)
 
def DFS2(grid, check_list2, x, y):
    check_list2[x][y] = True
    # 从终点到起点，只能下左
    for dx, dy in [(0,-1), (-1,0)]:
        nx, ny = x+dx, y+dy
        # 如果不越界，且不为墙壁，且未被检查过
        if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 0 and check_list2[nx][ny] == False:
            # 执行DFS
            DFS2(grid, check_list2, nx, ny)
 
# 初始化输入
n, m = map(int, input().split())
grid = [[0] * m for _ in range(n)]
# 构建两个检查数组，分别用于正向搜寻和逆向搜寻
check_list1 = [[False] * m for _ in range(n)]
check_list2 = [[False] * m for _ in range(n)]
# 输入墙壁方格的数量和坐标
wall_num = int(input())
for _ in range(wall_num):
    x, y = map(int, input().split())
    grid[x][y] = 1
    check_list1[x][y] = True
    check_list2[x][y] = True
# 第一次DFS：从起点往终点进行
x, y = 0, 0
check_list1[x][y] = True
DFS1(grid, check_list1, x, y)
 
# 退出DFS搜索后，check_list1中尚未搜寻过的点，即为【不可达方格】
# 计算check_list1中值为False的数目，即为【不可达方格】的数目
unreachable_num = 0
for i in range(n):
    for j in range(m):
        if check_list1[i][j] == False:
            unreachable_num += 1
 
# 第二次DFS：从终点往起点进行
x, y = n-1, m-1
DFS2(grid, check_list2, x, y)
# 退出DFS搜索后，check_list2中尚未搜寻过且在check_list1中搜索寻过的点，即为【陷阱方格】
# 计算check_list2中值为False且在check_list1中值为True的数目，即为【陷阱方格】的数目
trap_num = 0
for i in range(n):
    for j in range(m):
        if check_list2[i][j] == False and check_list1[i][j] == True:
            trap_num += 1
 
# 分别输出【陷阱方格】和【不可达方格】的数目，用空格隔开即为答案
print(trap_num, unreachable_num)

Java

import java.util.*;

public class Main {
    static int n, m;

    static void DFS1(int[][] grid, boolean[][] checkList1, int x, int y) {
        checkList1[x][y] = true;
        // From start to end, you can only go up or right
        int[][] directions = {{0, 1}, {1, 0}};
        for (int[] dir : directions) {
            int dx = dir[0];
            int dy = dir[1];
            int nx = x + dx;
            int ny = y + dy;
            // If it's not out of bounds, not a wall, and hasn't been checked
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0 && !checkList1[nx][ny]) {
                // Perform DFS
                DFS1(grid, checkList1, nx, ny);
            }
        }
    }

    static void DFS2(int[][] grid, boolean[][] checkList2, int x, int y) {
        checkList2[x][y] = true;
        // From end to start, you can only go down or left
        int[][] directions = {{0, -1}, {-1, 0}};
        for (int[] dir : directions) {
            int dx = dir[0];
            int dy = dir[1];
            int nx = x + dx;
            int ny = y + dy;
            // If it's not out of bounds, not a wall, and hasn't been checked
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0 && !checkList2[nx][ny]) {
                // Perform DFS
                DFS2(grid, checkList2, nx, ny);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int[][] grid = new int[n][m];
        boolean[][] checkList1 = new boolean[n][m];
        boolean[][] checkList2 = new boolean[n][m];

        int wallNum = scanner.nextInt();

        for (int i = 0; i < wallNum; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            grid[x][y] = 1;
            checkList1[x][y] = true;
            checkList2[x][y] = true;
        }

        // First DFS: From start to end
        int x = 0, y = 0;
        checkList1[x][y] = true;
        DFS1(grid, checkList1, x, y);

        int unreachableNum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!checkList1[i][j]) {
                    unreachableNum++;
                }
            }
        }

        // Second DFS: From end to start
        x = n - 1;
        y = m - 1;
        DFS2(grid, checkList2, x, y);

        int trapNum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!checkList2[i][j] && checkList1[i][j]) {
                    trapNum++;
                }
            }
        }

        System.out.println(trapNum + " " + unreachableNum);
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

int n, m;

void DFS1(vector<vector<int>>& grid, vector<vector<bool>>& check_list1, int x, int y) {
    check_list1[x][y] = true;
    // From start to end, you can only go up or right
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}};
    for (const auto& dir : directions) {
        int dx = dir.first;
        int dy = dir.second;
        int nx = x + dx;
        int ny = y + dy;
        // If it's not out of bounds, not a wall, and hasn't been checked
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0 && !check_list1[nx][ny]) {
            // Perform DFS
            DFS1(grid, check_list1, nx, ny);
        }
    }
}

void DFS2(vector<vector<int>>& grid, vector<vector<bool>>& check_list2, int x, int y) {
    check_list2[x][y] = true;
    // From end to start, you can only go down or left
    vector<pair<int, int>> directions = {{0, -1}, {-1, 0}};
    for (const auto& dir : directions) {
        int dx = dir.first;
        int dy = dir.second;
        int nx = x + dx;
        int ny = y + dy;
        // If it's not out of bounds, not a wall, and hasn't been checked
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0 && !check_list2[nx][ny]) {
            // Perform DFS
            DFS2(grid, check_list2, nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> check_list1(n, vector<bool>(m, false));
    vector<vector<bool>> check_list2(n, vector<bool>(m, false));

    int wall_num;
    cin >> wall_num;

    for (int i = 0; i < wall_num; i++) {
        int x, y;
        cin >> x >> y;
        grid[x][y] = 1;
        check_list1[x][y] = true;
        check_list2[x][y] = true;
    }

    // First DFS: From start to end
    int x = 0, y = 0;
    check_list1[x][y] = true;
    DFS1(grid, check_list1, x, y);

    int unreachable_num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!check_list1[i][j]) {
                unreachable_num++;
            }
        }
    }

    // Second DFS: From end to start
    x = n - 1;
    y = m - 1;
    DFS2(grid, check_list2, x, y);

    int trap_num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!check_list2[i][j] && check_list1[i][j]) {
                trap_num++;
            }
        }
    }

    cout << trap_num << " " << unreachable_num << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

/* ----------- 全局数据 ----------- */
int n, m;                    // 地图行列

/* ---------- 4 个方向数组 ---------- */
/* 起点 DFS 只允许“右、下”，终点 DFS 只允许“左、上” */
const int dirStart[2][2] = { {0, 1}, {1, 0} };   // (dx,dy)
const int dirEnd  [2][2] = { {0,-1}, {-1, 0} };

/* ------- 起点到终点方向的 DFS ------- */
void DFSStart(int **grid, char **vis, int x, int y)
{
    vis[x][y] = 1;                 // 标记已访问

    for (int k = 0; k < 2; ++k) {
        int nx = x + dirStart[k][0];
        int ny = y + dirStart[k][1];

        /* 边界、安全、未访问才递归 */
        if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
            grid[nx][ny] == 0 && !vis[nx][ny])
        {
            DFSStart(grid, vis, nx, ny);
        }
    }
}

/* ------- 终点到起点方向的 DFS ------- */
void DFSEnd(int **grid, char **vis, int x, int y)
{
    vis[x][y] = 1;

    for (int k = 0; k < 2; ++k) {
        int nx = x + dirEnd[k][0];
        int ny = y + dirEnd[k][1];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
            grid[nx][ny] == 0 && !vis[nx][ny])
        {
            DFSEnd(grid, vis, nx, ny);
        }
    }
}

int main(void)
{
    /* ---------- 输入基本参数 ---------- */
    if (scanf("%d %d", &n, &m) != 2) return 0;

    /* 动态申请二维数组 */
    int  **grid = (int **) malloc(n * sizeof(int *));
    char **vis1 = (char**) malloc(n * sizeof(char*));   // 起点可达
    char **vis2 = (char**) malloc(n * sizeof(char*));   // 终点可达
    for (int i = 0; i < n; ++i) {
        grid[i] = (int *)  calloc(m, sizeof(int));
        vis1[i] = (char*) calloc(m, sizeof(char));
        vis2[i] = (char*) calloc(m, sizeof(char));
    }

    /* ---------- 读取墙体 ---------- */
    int wallNum;  scanf("%d", &wallNum);
    for (int i = 0; i < wallNum; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        grid[x][y] = 1;     // 1 代表墙
        vis1[x][y] = 1;     // 提前标记“已访问”
        vis2[x][y] = 1;
    }

    /* ---------- 第一次 DFS：起点 -> 终点 (仅右/下) ---------- */
    if (grid[0][0] == 0) DFSStart(grid, vis1, 0, 0);

    int unreachable = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (!vis1[i][j]) ++unreachable;

    /* ---------- 第二次 DFS：终点 -> 起点 (仅左/上) ---------- */
    if (grid[n-1][m-1] == 0) DFSEnd(grid, vis2, n-1, m-1);

    int trap = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (vis1[i][j] && !vis2[i][j]) ++trap;

    /* ---------- 输出结果 ---------- */
    printf("%d %d\n", trap, unreachable);

    /* 释放内存 */
    for (int i = 0; i < n; ++i) {
        free(grid[i]); free(vis1[i]); free(vis2[i]);
    }
    free(grid); free(vis1); free(vis2);
    return 0;
}

Node JavaScript

// 读取全部输入
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);

let idx = 0;
const n = data[idx++];          // 行数
const m = data[idx++];          // 列数

// 地图，0=空地 1=墙
const grid = Array.from({ length: n }, () => Array(m).fill(0));
// 两张访问表
const visFromStart = Array.from({ length: n }, () => Array(m).fill(false));
const visFromEnd   = Array.from({ length: n }, () => Array(m).fill(false));

const wallNum = data[idx++];
for (let i = 0; i < wallNum; ++i) {
    const x = data[idx++];
    const y = data[idx++];
    grid[x][y] = 1;
    visFromStart[x][y] = true;  // 墙体直接视作已访问，后续无需再进栈
    visFromEnd[x][y]   = true;
}

/* ---------- 第一次 DFS/BFS：从 (0,0) 只能向右或向下 ---------- */
const stack1 = [];
if (grid[0][0] === 0) {         // 起点若非墙才入栈
    stack1.push([0, 0]);
    visFromStart[0][0] = true;
}
const dir1 = [[0, 1], [1, 0]];  // 右、下
while (stack1.length) {
    const [x, y] = stack1.pop();
    for (const [dx, dy] of dir1) {
        const nx = x + dx, ny = y + dy;
        if (nx < n && ny < m && !visFromStart[nx][ny] && grid[nx][ny] === 0) {
            visFromStart[nx][ny] = true;
            stack1.push([nx, ny]);
        }
    }
}

let unreachable = 0;
for (let i = 0; i < n; ++i)
    for (let j = 0; j < m; ++j)
        if (!visFromStart[i][j]) ++unreachable;

/* ---------- 第二次 DFS/BFS：从 (n-1,m-1) 只能向左或向上 ---------- */
const stack2 = [];
if (grid[n - 1][m - 1] === 0) {
    stack2.push([n - 1, m - 1]);
    visFromEnd[n - 1][m - 1] = true;
}
const dir2 = [[0, -1], [-1, 0]];  // 左、上
while (stack2.length) {
    const [x, y] = stack2.pop();
    for (const [dx, dy] of dir2) {
        const nx = x + dx, ny = y + dy;
        if (nx >= 0 && ny >= 0 && !visFromEnd[nx][ny] && grid[nx][ny] === 0) {
            visFromEnd[nx][ny] = true;
            stack2.push([nx, ny]);
        }
    }
}

let trap = 0;
for (let i = 0; i < n; ++i)
    for (let j = 0; j < m; ++j)
        if (visFromStart[i][j] && !visFromEnd[i][j]) ++trap;

console.log(`${trap} ${unreachable}`);

Go

package main

import (
        "bufio"
        "fmt"
        "os"
)

/* 坐标结构体 */
type node struct{ x, y int }

func main() {
        in := bufio.NewReader(os.Stdin)

        var n, m int
        fmt.Fscan(in, &n, &m)

        // 地图 0=空地 1=墙
        grid := make([][]int, n)
        vis1 := make([][]bool, n) // 从起点可达
        vis2 := make([][]bool, n) // 从终点可达
        for i := 0; i < n; i++ {
                grid[i] = make([]int, m)
                vis1[i] = make([]bool, m)
                vis2[i] = make([]bool, m)
        }

        var wallNum int
        fmt.Fscan(in, &wallNum)
        for i := 0; i < wallNum; i++ {
                var x, y int
                fmt.Fscan(in, &x, &y)
                grid[x][y] = 1
                vis1[x][y] = true // 先标记墙为已访问
                vis2[x][y] = true
        }

        /* ---------- 第一次 DFS/BFS ---------- */
        stack1 := []node{}
        if grid[0][0] == 0 {
                stack1 = append(stack1, node{0, 0})
                vis1[0][0] = true
        }
        dir1 := []node{{0, 1}, {1, 0}} // 右、下
        for len(stack1) > 0 {
                cur := stack1[len(stack1)-1]
                stack1 = stack1[:len(stack1)-1]
                for _, d := range dir1 {
                        nx, ny := cur.x+d.x, cur.y+d.y
                        if nx < n && ny < m && !vis1[nx][ny] && grid[nx][ny] == 0 {
                                vis1[nx][ny] = true
                                stack1 = append(stack1, node{nx, ny})
                        }
                }
        }

        unreachable := 0
        for i := 0; i < n; i++ {
                for j := 0; j < m; j++ {
                        if !vis1[i][j] {
                                unreachable++
                        }
                }
        }

        /* ---------- 第二次 DFS/BFS ---------- */
        stack2 := []node{}
        if grid[n-1][m-1] == 0 {
                stack2 = append(stack2, node{n - 1, m - 1})
                vis2[n-1][m-1] = true
        }
        dir2 := []node{{0, -1}, {-1, 0}} // 左、上
        for len(stack2) > 0 {
                cur := stack2[len(stack2)-1]
                stack2 = stack2[:len(stack2)-1]
                for _, d := range dir2 {
                        nx, ny := cur.x+d.x, cur.y+d.y
                        if nx >= 0 && ny >= 0 && !vis2[nx][ny] && grid[nx][ny] == 0 {
                                vis2[nx][ny] = true
                                stack2 = append(stack2, node{nx, ny})
                        }
                }
        }

        trap := 0
        for i := 0; i < n; i++ {
                for j := 0; j < m; j++ {
                        if vis1[i][j] && !vis2[i][j] {
                                trap++
                        }
                }
        }

        fmt.Printf("%d %d\n", trap, unreachable)
}

时空复杂度

时间复杂度：O(NM)。搜索需要遍历grid二维数组中的每一个位置。

空间复杂度：O(NM)。两个检查数组所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！
课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接OD真题汇总(持续更新)
绿色聊天软件戳 od1441或了解更多

亚马逊云科技技术品牌专区

更多推荐

WRB1205S-1WR2 与钡特电源 VB1-12S05S 参数规格解析｜ 1W 宽压输入隔离 DC-DC 工业电源模块性能拆解

亚马逊云科技技术品牌专区

AI 前沿日报 | 2026年7月10日

法国竞争管理局正对英伟达推进反垄断调查，核心指控围绕市场对其 CUDA 平台的高度依赖，以及英伟达对 CoreWeave 等 AI 云计算公司的投资。若落地，法国将成全球首个对英伟达提出反垄断指控的监管机构。Reflect 功能向已开记忆功能的用户开放，可回看过去 1-12 个月的 Claude 使用活动，并按"委派、描述、辨别、审慎"四个维度生成使用总结与改进建议。据 IT之家援引的消息，三星正

亚马逊云科技技术品牌专区

基于 Spring Boot 的现代化微服务架构设计与实践

本文以当前主流的 Java/Spring Boot 技术栈为核心，设计一套匹配现代化业务需求的微服务架构。我们将从技术选型、架构分层、核心组件、部署运维及演进路线五个维度展开，提供一套可直接落地的架构蓝图与实践指导。本文设计的 Spring Boot 微服务架构，融合了成熟的 Spring Cloud 生态与云原生实践，在保证开发效率的同时，兼顾了高性能、高可用与可维护性。团队在落地时，应结合具体

亚马逊云科技技术品牌专区

所有评论(0)

查看更多评论

闭着眼睛学算法

@weixin_48157259

已为社区贡献14条内容

【双机位A卷】华为OD笔试之【DFS/BFS】双机位A-陷阱方格【Py/Java/C++/C/JS/Go六种语言OD独家双机位A卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

文章目录

相关推荐阅读

题目描述与示例

题目描述

输入描述

输出描述

示例一

输入

输出

示例二

输入

输出

说明

解题思路

不可达方格的判断

逆向路径的概念

陷阱方格的判断

其他特殊处理

代码

解法一：BFS

Python

Java

C++

C

Node JavaScript

Go

解法二：DFS

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

华为OD算法/大厂面试高频题算法练习冲刺训练

所有评论(0)

闭着眼睛学算法

【双机位A卷】华为OD笔试之【DFS/BFS】双机位A-陷阱方格【Py/Java/C++/C/JS/Go六种语言OD独家双机位A卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

文章目录

相关推荐阅读

题目描述与示例

题目描述

输入描述

输出描述

示例一

输入

输出

示例二

输入

输出

说明

解题思路

不可达方格的判断

逆向路径的概念

陷阱方格的判断

其他特殊处理

代码

解法一：BFS

Python

Java

C++

C

Node JavaScript

Go

解法二：DFS

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

华为OD算法/大厂面试高频题算法练习冲刺训练

所有评论(0)

温馨提示：您尚未绑定手机号

闭着眼睛学算法