打卡题单做到第 2968 题正好碰上 P5962 [BalticOI 2004] Ships (Day1)。说实话第一眼看到 BalticOI 这个前缀我下意识觉得又是一道绕弯子的思维题结果把题面读完才发现这道题的核心就是最朴素的 C 二维数组 搜索遍历特别适合用来巩固连通块处理的基本功。今天就把我从读题到 AC 的完整过程拆开讲一遍包括代码实现、踩过的坑以及如果题目再多问一句“船的形态是否合法”该怎么继续写。适合看这篇的人主要有两类一类是刚开始系统刷信奥题想找一道典型的网格搜索题练手另一类是已经会 DFS/BFS但总在细节上翻车的选手——比如数组开小、读入出错、递归爆栈。这道题不算难但恰恰是这种“不算难”的题最能暴露代码基本功的问题。1. 从题面到模型把“船”翻译成二维数组问题1.1 题面真正要求的是一件事连通块计数这道题在 OJ 上的常见描述是这样的给定一张 n 行 m 列的地图地图上的每个格子要么是水用.表示要么是船体的一部分用X表示。彼此相邻的 X 格子属于同一艘船请问地图上一共有多少艘船最大的一艘船占了多少个格子。我第一次刷这道题的时候看到“船”这个字脑子里先想到的是各种复杂的几何判断后来意识到完全想多了。所有题目信息翻译成程序语言就是一句话在二维矩阵中把相邻的 X 当成一个集合统计集合的数量和每个集合的大小。这是典型的连通块计数问题在信奥里边属于搜索专题的入门必修题和数“地图上有多少个岛屿”“多少个省份”是同一套模型。这里最关键的建模转换是把“船”这个生活概念翻译成“连通块”这个算法概念。船体的每一格就是一个节点上下左右相邻的格子就是一条边所有能互相到达的节点构成一艘船。整个过程不需要任何几何知识只需要知道当前格子周围四个方向上有哪些邻居。1.2 用 C 表示地图二维数组和字符串数组都行地图的存储方式我见过有人用vectorvectorchar有人用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 左右递归太深就会爆栈程序直接 RERuntime Error。我个人的经验是如果题目数据范围在 1000×1000 以内DFS 通常没问题但如果看到 n×m 可能达到 10^6 以上最好直接改用 BFS。2.3 BFS 可以完全避免爆栈问题BFS广度优先搜索用队列实现不占用系统调用栈所以不存在递归深度的问题。核心写法就是起点入队标记访问队列不为空时取队首遍历四个邻居把符合条件的邻居入队并标记。#include queue int bfs(int sx, int sy) { queuepairint, 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 两种方案怎么选我的判断标准对比维度DFS 递归BFS 队列代码长度更短稍长爆栈风险有数据大时明显几乎没有实现难度容易容易推荐场景n×m 较小n×m 较大或递归深度不可控我的建议是如果是平时练题两种都写一遍因为换着写能加深理解如果是正式比赛先看数据范围再决定。实在不确定的话直接上 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 里面有两个好处一是全局变量默认初始化为 0vis不需要手动 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 主程序主循环主程序要做的事情只有三步读入 n, m 和整张地图。双重循环从头到尾扫一遍地图。遇到没访问过的 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 字节约 1MBbool数组通常也是 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、所有船都在角落、船和船之间只隔一个点这些情况。把这些数据跑顺了网格搜索题的基本功就真正扎实了。