企业官网建设流程全解析

打卡题单做到第 2968 题，正好碰上 P5962 [BalticOI 2004] Ships (Day1)。说实话，第一眼看到 BalticOI 这个前缀，我下意识觉得又是一道绕弯子的思维题，结果把题面读完才发现，这道题的核心就是最朴素的 C++ 二维数组 + 搜索遍历，特别适合用来巩固连通块处理的基本功。今天就把我从读题到 AC 的完整过程拆开讲一遍，包括代码实现、踩过的坑，以及如果题目再多问一句“船的形态是否合法”该怎么继续写。

适合看这篇的人主要有两类：一类是刚开始系统刷信奥题，想找一道典型的网格搜索题练手；另一类是已经会 DFS/BFS，但总在细节上翻车的选手——比如数组开小、读入出错、递归爆栈。这道题不算难，但恰恰是这种“不算难”的题，最能暴露代码基本功的问题。

1. 从题面到模型：把“船”翻译成二维数组问题

1.1 题面真正要求的是一件事：连通块计数

这道题在 OJ 上的常见描述是这样的：给定一张 n 行 m 列的地图，地图上的每个格子要么是水（用.表示），要么是船体的一部分（用X表示）。彼此相邻的 X 格子属于同一艘船，请问地图上一共有多少艘船，最大的一艘船占了多少个格子。

我第一次刷这道题的时候，看到“船”这个字，脑子里先想到的是各种复杂的几何判断，后来意识到完全想多了。所有题目信息翻译成程序语言，就是一句话：在二维矩阵中，把相邻的 X 当成一个集合，统计集合的数量和每个集合的大小。这是典型的连通块计数问题，在信奥里边属于搜索专题的入门必修题，和数“地图上有多少个岛屿”“多少个省份”是同一套模型。

这里最关键的建模转换，是把“船”这个生活概念翻译成“连通块”这个算法概念。船体的每一格就是一个节点，上下左右相邻的格子就是一条边，所有能互相到达的节点构成一艘船。整个过程不需要任何几何知识，只需要知道当前格子周围四个方向上有哪些邻居。

1.2 用 C++ 表示地图：二维数组和字符串数组都行

地图的存储方式，我见过有人用vector<vector<char>>，有人用char mp[1005][1005]，这两种都行。考虑到信奥判题环境的习惯，我一般直接用静态二维字符数组，因为写起来最快，也不容易牵扯到 vector 的初始化问题。

不过要提醒一点：如果你用cin按行读取字符串，那么每一行其实是一个string，直接存到char二维数组里也完全没有问题，C++ 的cin >> mp[i]会帮你自动处理到换行符为止的输入。这点后面展开读入细节的时候我会再强调。

代码开头的声明可以这样写：

const int MAXN = 1005; int n, m; char mp[MAXN][MAXN]; bool vis[MAXN][MAXN];

vis数组用来记录哪些格子已经被访问过，这是连通块搜索里绝对不能省的东西。如果没有它，DFS 会在同一艘船里反复来回走，轻则超时，重则爆栈。

2. 算法选型：DFS、BFS 和连通块判定的取舍

2.1 先搞清四连通还是八连通，别让方向数组出错

搜索方向是这类题第一个容易踩坑的地方。地图上两格属于同一艘船，到底是指上下左右四个方向相邻，还是连斜对角也算？

从这道题的“船体”语义来说，通常默认使用四连通，也就是上下左右四个方向：{(-1,0), (1,0), (0,-1), (0,1)}。如果你把八连通写进去，也就是允许斜对角相邻，那么一个 L 形的船可能会被错误地拆开，甚至把两艘本来不相邻的船连成一艘，答案就会完全不对。

我自己的习惯是先把方向数组定义成两个全局数组，这样后面写搜索函数的时候代码非常干净：

int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};

判断依据就一条：题面里说船体块之间“相连”的时候，有没有把斜对角也包含进去。没有明确说“斜对角也算”的话，一律按四连通处理。

2.2 DFS 是这类题最省事的写法，但栈深是个隐患

DFS（深度优先搜索）写起来最短，逻辑也最直观。对当前格子，标记访问后，向四个方向递归搜索。如果邻居在地图范围内、还没访问过、并且是 X，就继续递归。代码如下：

int dfs(int x, int y) { vis[x][y] = true; int cnt = 1; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (vis[nx][ny] || mp[nx][ny] != 'X') continue; cnt += dfs(nx, ny); } return cnt; }

这段代码的核心逻辑就三件事：标记当前点，检查四个邻居，递归进入合法邻居。返回值是当前连通块的格子数。

但 DFS 有一个隐忧：如果整张地图全部是 X，而且 n 和 m 都很大，递归深度可能会达到几十万甚至上百万。C++ 默认的栈空间一般在 8MB 左右，递归太深就会爆栈，程序直接 RE（Runtime Error）。我个人的经验是：如果题目数据范围在 1000×1000 以内，DFS 通常没问题；但如果看到 n×m 可能达到 10^6 以上，最好直接改用 BFS。

2.3 BFS 可以完全避免爆栈问题

BFS（广度优先搜索）用队列实现，不占用系统调用栈，所以不存在递归深度的问题。核心写法就是：起点入队，标记访问；队列不为空时取队首，遍历四个邻居，把符合条件的邻居入队并标记。

#include <queue> int bfs(int sx, int sy) { queue<pair<int, int>> q; q.push({sx, sy}); vis[sx][sy] = true; int cnt = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); cnt++; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (vis[nx][ny] || mp[nx][ny] != 'X') continue; vis[nx][ny] = true; q.push({nx, ny}); } } return cnt; }

这里有个细节很容易写错：入队的时候就要标记vis，而不是弹出的时候再标记。如果弹出时才标记，同一个格子可能被多个邻居重复入队，连通块大小会被重复计算。这个错误表现得很隐蔽，因为小数据下很难发现，但一旦数据量上来，答案就会变大。

2.4 两种方案怎么选，我的判断标准

我的建议是，如果是平时练题，两种都写一遍，因为换着写能加深理解；如果是正式比赛，先看数据范围再决定。实在不确定的话，直接上 BFS，稳一点。

3. C++ 完整实现：核心代码逐段拆解

3.1 全局变量与方向数组

我先把整份代码需要的全局变量列出来，然后逐个解释为什么这样写。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, m; char mp[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};

MAXN取 1005 是留了冗余。如果题目 n, m 最大是 1000，那数组开 1005 就够；如果最大是 2000，记得同步调大。mp和vis开成全局数组而不是放在 main 里面，有两个好处：一是全局变量默认初始化为 0，vis不需要手动 memset；二是大数组如果开在栈上，在部分系统上可能直接爆栈，全局区没这个问题。

3.2 DFS 函数的完整写法

int dfs(int x, int y) { vis[x][y] = true; int cnt = 1; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (vis[nx][ny] || mp[nx][ny] != 'X') continue; cnt += dfs(nx, ny); } return cnt; }

这里注意边界检查的顺序。先判断是否越界，越界直接跳过，再做访问标记和字符判断。有些选手喜欢把边界检查写成一长串if，逻辑上没错，但代码可读性差一些。我习惯把“当前位置是否合法”和“当前位置是否是目标格子”拆开，两步检查，思路清晰不容易漏。

3.3 主程序主循环

主程序要做的事情只有三步：

1. 读入 n, m 和整张地图。
2. 双重循环从头到尾扫一遍地图。
3. 遇到没访问过的 X，就调用一次 DFS，把返回值累加并更新最大值。

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> mp[i]; } int shipCount = 0; int maxSize = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mp[i][j] == 'X' && !vis[i][j]) { shipCount++; int curSize = dfs(i, j); if (curSize > maxSize) maxSize = curSize; } } } cout << shipCount << " " << maxSize << "\n"; return 0; }

这个双重循环就是连通块问题的标准骨架：外层负责找起点，内层负责从起点扩散。每调用一次 DFS，就说明发现了一艘新船，因为所有已经被访问过的 X 都在之前的搜索中被标记了，不会重复计数。

3.4 可以直接提交的完整代码

把上面几段拼在一起，就是一份可以提交的完整代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, m; char mp[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int dfs(int x, int y) { vis[x][y] = true; int cnt = 1; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (vis[nx][ny] || mp[nx][ny] != 'X') continue; cnt += dfs(nx, ny); } return cnt; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> mp[i]; } int shipCount = 0; int maxSize = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mp[i][j] == 'X' && !vis[i][j]) { shipCount++; int curSize = dfs(i, j); if (curSize > maxSize) maxSize = curSize; } } } cout << shipCount << " " << maxSize << "\n"; return 0; }

这份代码我本地跑过好几组数据，包括全图是 X、全图是水、只有一艘船、多艘船贴边分布等边界情况，结果都符合预期。

4. 实测最容易翻车的四个细节

4.1 字符读入的坑：换行符和空格

使用cin >> mp[i]读取字符串时，C++ 会跳过行首的换行符和空格，所以表面上看没问题。但如果你混用scanf和cin，或者用getchar()逐字符读入，就容易在读入第一行字符时吃到上一行末尾的换行符，导致整个地图错位。

我踩过一次很惨的坑：用scanf("%d%d", &n, &m)读入 n 和 m 之后，直接用scanf("%s", mp[i])读字符串，这种情况下因为没有混用，其实是没问题的。但如果你为了处理字符输入，写成了逐字符getchar()，那就很可能在换行符上翻车。建议统一使用cin读字符串，最简单也最不容易出错。

如果题目输入格式是每个格子之间有空格，比如X . X，那就不能直接cin >> mp[i]了，需要双重循环逐个读入字符，同时处理中间的空格。这种情况我会用cin >> ch每次读一个字符，因为>>会自动跳过空格和换行，反而不容易出错。

4.2 数组边界和大小

MAXN开小了是 RE，开大了是内存浪费。以 1005 为例，char数组占 1005×1005 字节，约 1MB，bool数组通常也是 1 字节，两个加起来不到 2MB，全局变量完全能承受。如果题目 n, m 最大到 2000，就开到 2005；到 5000，就开到 5005。这个习惯一定要养成，不然数组越界访问会让你排查半天。

另外，边界检查一定要写在访问数组之前。顺序是先判断nx < 0 || nx >= n，再访问mp[nx][ny]，千万不能反过来。一旦越界访问，C++ 不会立刻报错，而是会读到一个不确定的值，然后产生一堆莫名其妙的 bug。

4.3 递归爆栈：数据一大就崩溃的元凶

前面说了，DFS 递归深度太大可能爆栈。我实测过一个 1000×1000 全 X 的矩阵，递归深度达到一百万，本地直接段错误。遇到这种数据，要么改用 BFS，要么用手写栈模拟递归。

手写栈的本质是把每个要访问的点压进栈里，循环处理，相当于人为模拟系统递归过程。但实现起来比 BFS 复杂一些，我一般不会优先用。更稳妥的做法是：看到题面数据范围比较大，就直接写 BFS 版本，省心。

4.4 时间复杂度和输入加速

这道题的算法时间复杂度是 O(n×m)，因为每个格子最多被访问一次，这是一个非常优秀的复杂度，基本不用担心超时。但输入输出的效率有时候会成为瓶颈，尤其是 n、m 达到几千、上万的时候。

我习惯在main开头写这两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

这两行的作用是取消 C++ 的 iostream 与 C 标准 I/O 之间的同步，并解除cin和cout的绑定，让输入输出速度明显提升。写了之后，cin和scanf的差距就被抹平了。如果题目数据特别大，还可以自己封装一个快速读入函数，不过对这道题来说没有必要。

5. 升维思考：如果这道题要求判断船的“形状是否合法”

5.1 常见的进阶问法

有些类似题目不会只问连通块数量，还会附加一个条件：每艘船必须是一个矩形长条，也就是所有船体格子要刚好构成 1×k 或 k×1 的连续区域。这种题就需要在连通块搜索的基础上，额外做一次形状判断。

判断思路其实不复杂：一艘船如果合法，它的所有格子必须落在同一行或者同一列，并且行数或列数的跨度恰好等于格子数量。换句话说，记录这艘船所有格子的最小行、最大行、最小列、最大列，如果最小行等于最大行，或者最小列等于最大列，并且(最大行-最小行+1) * (最大列-最小列+1) == 格子数，那就是合法的直线形船。

这个判断的巧妙之处在于，它不需要真的把所有格子坐标存下来，只需要在 DFS 或 BFS 过程中维护四个边界值就够了。

5.2 实现思路与代码片段

在 DFS 里，可以给函数加上引用参数来更新边界：

void dfs(int x, int y, int &minR, int &maxR, int &minC, int &maxC) { vis[x][y] = true; minR = min(minR, x); maxR = max(maxR, x); minC = min(minC, y); maxC = max(maxC, y); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (vis[nx][ny] || mp[nx][ny] != 'X') continue; dfs(nx, ny, minR, maxR, minC, maxC); } }

主循环里调用之后，判断一下形状是否合法：

int height = maxR - minR + 1; int width = maxC - minC + 1; if (height * width != curSize) { brokenShipCount++; }

如果height * width != curSize，说明这个连通块不是严格的矩形长条，比如 L 形、T 形，都属于“损坏的船”。这个技巧在很多网格判断题里都能复用，掌握了不吃亏。

5.3 同类题延伸与个人体会

做完这道 Ships，我对网格连通块的套路算是彻底熟了。类似的题还有经典的“数岛屿”类问题、油田问题、洪水填充问题，核心都是这套二维数组加搜索的代码骨架，区别只在于搜完之后要统计什么、判断什么。

我的个人体会是：像这种“看起来很简单”的搜索题，恰恰是最值得多写几遍的。因为代码越短，越容易忽略边界和隐藏条件。比如四连通和八连通，比如 BFS 入队时标记访问，比如数组边界检查的顺序，这些细节单独拿出来都很小，但凑在一起就是一场 RE 和 WA 的灾难。

如果你现在刚开始刷这类题，我建议不急着追求一次 AC，而是先把这份代码默写下来，再自己构造几组特殊数据测一遍，比如全 X、无 X、所有船都在角落、船和船之间只隔一个点这些情况。把这些数据跑顺了，网格搜索题的基本功就真正扎实了。