DFS 进阶如何判断连通块是否是矩形含完整代码在 DFS / BFS 学习中“连通块”是绕不开的话题。但你是否想过这样一个问题如何判断一个连通块的形状是不是矩形本文将从思路 → DFS 设计 → 代码实现 → 易错点一步步讲清楚。一、问题模型给定一个N × M的字符矩阵只包含两种字符字符含义#连通块.空地规则上下左右相邻的#属于同一个连通块要求判断该连通块是否构成一个完整的矩形二、什么是“矩形连通块”一个连通块是矩形当且仅当连通块的最小外接矩形中没有空洞且所有格子都属于该连通块换句话说(最大行 - 最小行 1) × (最大列 - 最小列 1) 连通块大小三、DFS 需要返回什么信息为了判断矩形DFS 不能只返回“数量”。我们需要返回5 个关键信息信息含义cnt连通块中#的数量x1最小行号x2最大行号y1最小列号y2最大列号四、DFS 返回值设计核心structnode{intcnt;// 连通块大小intx1,x2;// 行边界inty1,y2;// 列边界};DFS 的职责从当前点出发收集整个连通块的边界信息向上合并五、DFS 核心代码 ✅nodedfs(intx,inty){vis[x][y]true;node tmp;tmp.cnt1;tmp.x1tmp.x2x;tmp.y1tmp.y2y;for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(!vis[nx][ny]a[nx][ny]#){node ntdfs(nx,ny);tmp.cntnt.cnt;tmp.x1min(tmp.x1,nt.x1);tmp.x2max(tmp.x2,nt.x2);tmp.y1min(tmp.y1,nt.y1);tmp.y2max(tmp.y2,nt.y2);}}returntmp;}六、主函数逻辑intmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)cina[i][j];intcnt10;// 非矩形连通块intcnt20;// 矩形连通块for(inti1;in;i){for(intj1;jm;j){if(!vis[i][j]a[i][j]#){node bdfs(i,j);intarea(b.x2-b.x11)*(b.y2-b.y11);if(areab.cnt)cnt2;elsecnt1;}}}coutcnt2endlcnt1;return0;}七、完整代码可直接提交 ✅#includebits/stdc.husingnamespacestd;constintN85;chara[N][N];boolvis[N][N];intn,m;intdx[4]{0,1,0,-1};intdy[4]{1,0,-1,0};structnode{intcnt;intx1,x2;inty1,y2;};nodedfs(intx,inty){vis[x][y]true;node tmp;tmp.cnt1;tmp.x1tmp.x2x;tmp.y1tmp.y2y;for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(!vis[nx][ny]a[nx][ny]#){node ntdfs(nx,ny);tmp.cntnt.cnt;tmp.x1min(tmp.x1,nt.x1);tmp.x2max(tmp.x2,nt.x2);tmp.y1min(tmp.y1,nt.y1);tmp.y2max(tmp.y2,nt.y2);}}returntmp;}intmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)cina[i][j];intcnt10,cnt20;for(inti1;in;i){for(intj1;jm;j){if(!vis[i][j]a[i][j]#){node bdfs(i,j);intarea(b.x2-b.x11)*(b.y2-b.y11);if(areab.cnt)cnt2;elsecnt1;}}}coutcnt2endlcnt1;return0;}八、给学生的总结口诀 ✅DFS 不只数个数边界信息一起拿。矩形面积若相等形状一定是方家。九、一句话总结判断连通块是不是矩形关键不是 DFS 会不会走而是 DFS 能不能告诉你这个块有多宽、有多高、有多少个格子。