✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

京东-2025.11.01

题目一：网络信号塔扩建

1️⃣：先对所有连通信号区进行 BFS/DFS 标记，为每个连通块分配编号并统计大小

2️⃣：对每个盲区位置，收集四个方向相邻的不同连通块，累加大小即可

3️⃣：时间复杂度 ，通过预处理避免重复计算

难度：中等

题目二：古堡探险机器人

1️⃣：状态设计为 ，其中 表示上一步的移动方向类型

2️⃣：使用 BFS 最短路搜索，转移时强制水平和竖直方向交替

3️⃣：起点两种状态都初始化为 步，终点取两种状态的最小值

难度：中等

1. 网络信号塔扩建

问题描述

K 小姐负责管理一个 的城市区域网络规划。在这个区域中，每个位置要么已经覆盖了信号（用 '' 表示），要么是信号盲区（用 '' 表示）。

为了改善网络覆盖，K 小姐计划在某一个信号盲区位置新建一座信号塔，使其变为有信号的区域。我们定义"连通信号区"为四连通的有信号区域（即区域内任意两个位置可以通过上下左右移动，仅经过有信号的位置互相到达）。

K 小姐想要知道每个位置的潜力：对于每个位置，如果原本已有信号，输出 ；如果原本是盲区，输出在该位置新建信号塔后，包含该位置的连通信号区的最大面积。

输入格式

第一行包含两个正整数 和 ，表示区域的行数和列数。

接下来 行，每行包含一个长度为 的字符串，字符串由 ''（信号盲区）和 ''（有信号区域）组成，描述区域的初始状态。

输出格式

输出 行，每行 个整数，中间用空格隔开。对于原本有信号的位置输出 ；对于原本是盲区的位置，输出在该位置新建信号塔后包含该位置的连通信号区的最大面积。

样例输入

3 3
xoo
oxo
xox

6 5
ooooo
oxxoo
xxxox
oxxoo
xooxx
ooooo

样例输出

5 0 0
0 6 0
3 0 5

0 0 0 0 0
0 12 12 0 0
13 1 12 0 12
0 9 19 0 0
9 0 0 19 19
0 0 0 0 0

样例	解释说明
样例1	在位置 新建信号塔后，能连通周围 个有信号位置，总面积为 。在位置 新建后，能将所有位置连通，面积为 。
样例2	在位置 新建信号塔后，可以将多个分散的信号区域连接起来，形成面积为 的最大连通区域。

数据范围

题解

这道题的关键在于理解如何高效地计算每个盲区位置新建信号塔后的连通区域大小。

核心思路

如果暴力做法，对每个盲区位置都进行一次 BFS/DFS 来计算连通块大小，时间复杂度会达到 ，对于 的规模会超时。

更聪明的做法是先预处理所有已有的信号区域，给每个连通块分配一个编号，并记录每个连通块的大小。然后对于每个盲区位置，只需要查看它上下左右四个方向相邻的不同连通块，把这些连通块的大小加起来，再加上自己这一个位置即可。

具体步骤

1. 预处理阶段：遍历整个网格，对每个有信号且未访问的位置进行 BFS/DFS，给这个连通块分配一个唯一编号，同时统计这个连通块的大小。用一个数组 id[i][j] 记录位置 属于哪个连通块，用 sz[k] 记录编号为 的连通块大小。

2. 计算答案：遍历每个位置，如果是有信号区域输出 。如果是盲区，检查上下左右四个方向的相邻位置，收集所有不同的连通块编号（注意去重，因为四个方向可能属于同一个连通块），将这些连通块的大小累加，最后加上当前位置本身的 。

复杂度分析

预处理阶段需要遍历整个网格一次，时间复杂度 。计算答案阶段也是遍历整个网格，每个位置最多检查 个方向，时间复杂度 。总时间复杂度 ，空间复杂度 ，可以轻松通过本题的数据范围。

这个做法的精妙之处在于通过预处理，把每个盲区位置的答案计算从 降低到了 （常数次数的查询和累加）。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

# 读入数据
n, m = map(int, input().split())
g = []
for _ in range(n):
    g.append(input())

# id 记录每个位置属于哪个连通块，sz 记录每个连通块的大小
id_map = [[0] * m for _ in range(n)]
sz = [0] * (n * m + 5)
cnt = 0  # 连通块编号计数器

# 四个方向
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# BFS 标记连通块
for i in range(n):
    for j in range(m):
        if g[i][j] == 'o' and id_map[i][j] == 0:
            cnt += 1
            q = deque([(i, j)])
            id_map[i][j] = cnt
            area = 1
            
            while q:
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < m and g[nx][ny] == 'o' and id_map[nx][ny] == 0:
                        id_map[nx][ny] = cnt
                        area += 1
                        q.append((nx, ny))
            
            sz[cnt] = area

# 计算每个位置的答案
ans = []
for i in range(n):
    row = []
    for j in range(m):
        if g[i][j] == 'o':
            row.append(0)
        else:
            # 收集四个方向的连通块编号并去重
            ids = set()
            for dx, dy in dirs:
                nx, ny = i + dx, j + dy
                if 0 <= nx < n and 0 <= ny < m and id_map[nx][ny] > 0:
                    ids.add(id_map[nx][ny])
            
            # 累加连通块大小
            total = 1  # 加上当前位置
            for cid in ids:
                total += sz[cid]
            row.append(total)
    
    ans.append(row)

# 输出结果
for row in ans:
    print(' '.join(map(str, row)))

• Cpp

#include <bits/stdc++.h>
using namespace std;

int n, m, id[505][505], sz[250005];
char g[505][505];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }
    
    int cnt = 0;
    queue<pair<int, int>> q;
    
    // BFS 标记所有连通块
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'o' && id[i][j] == 0) {
                cnt++;
                id[i][j] = cnt;
                q.push({i, j});
                int area = 1;
                
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k], ny = y + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                            g[nx][ny] == 'o' && id[nx][ny] == 0) {
                            id[nx][ny] = cnt;
                            area++;
                            q.push({nx, ny});
                        }
                    }
                }
                sz[cnt] = area;
            }
        }
    }
    
    // 计算并输出答案
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'o') {
                cout << 0;
            } else {
                // 收集相邻的不同连通块
                set<int> ids;
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m && id[ni][nj] > 0) {
                        ids.insert(id[ni][nj]);
                    }
                }
                
                int tot = 1;
                for (int cid : ids) {
                    tot += sz[cid];
                }
                cout << tot;
            }
            if (j + 1 < m) cout << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static char[][] grid;
    static int[][] idMap;
    static int[] size;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        grid = new char[n][m];
        idMap = new int[n][m];
        size = new int[n * m + 5];
        
        for (int i = 0; i < n; i++) {