因为想不到或者不知道这道题的算法是什么,我想枚举模拟,但是在枚举模拟的过程中,我发现,我模拟从一个串的开始到串的末尾,这个过程很难模拟出来,所以暴力做法也写不出来,最后,看官方题解以及问ai,才知道这道题要用BFS(广度优先搜索)BFS:为什么要用BFS这道题是一个连通块问题,等效于要求我们统计“不漏水”的水坑,bfs的核心思想就是从一个点开始,向四周扩散,所以这道题的要求很契合bfs具体思路用两个数组表示平移到上下左右用一个二维bool数组表示该格子是否被扫描过循环每个字符假如一个字符没被扫描过,并且是.,以它为头建造一个队列(存储pair),记住存入队列就马上标记(原因见下文).设定一个bool数来表示连通串是否有点在边界bfs寻找:首先判断当前的坐标是否在边界内,即使在边界,还是要把邻居找完,不然之后还是循环到邻居还是要再找,可能导致重复找邻居,效率低下.找邻居(注意判断坐标边界条件,将邻居push进队列,进队列就标记)进队列就标记的原因:如下例子所示:1. 2×2 地图的“包抄”过程假设四个点全是水坑.A—— 起点B—— A 的下方邻居C—— A 的右方邻居D——B 的右方邻居同时也是 C 的下方邻居第一步处理 AA 看向四周发现了 B 和 C 。A 把 B 和 C 都丢进队列排队。此时队列[B, C]。注意此时 B 和 C 还没出队所以还没被贴上cg1的标签。第二步轮到 B 出队B 贴上标签cg[1][0]1。B 看向它的邻居发现了D。B 发现 D 还没贴标签于是把D 丢进队列。此时队列[C, D]。注意此时 D 已经在排队了但因为还没出队它的标签cg[1][1]依然是 0。第三步轮到 C 出队C 贴上标签cg[0][1]1。C 看向它的邻居也发现了D关键冲突点C 检查cg[1][1]发现竟然是0因为 D 还在后面排队呢没轮到它贴标签。C 以为 D 是个没人管的“新发现”于是又把 D 丢进了一次队列。最终队列[D, D]。2. 为什么这很可怕虽然 和 互不相识但它们像两个不沟通的部门同时看中了同一个员工D。在一个大迷宫里任何一个空格子比如 通常都有 4 个邻居。这意味着如果你不在入队那一刻就贴上标签这个格子可能会被它的上下左右邻居每人举报一次。在你的while循环里原本这个格子只需要处理 1 次现在却要处理 4 次。而这 4 次处理又会引发出更多的重复……这种冗余会像病毒一样在你的队列里疯狂繁殖。假如队列空后bool数不变,那么count代码:#include bits/stdc.h using i64 long long; int dx[] {1, -1, 0, 0}; int dy[] {0, 0, 1, -1}; void solve(){ int h, w; std::cin h w; std::vectorstd::string s(h); for(int i 0; i h; i){ std::cin s[i]; } std::vectorstd::vectorbool cg(h,std::vectorbool (w,0)); int count 0; for(int i 0; i h; i){ for(int j 0; j w; j){ if(s[i][j] . cg[i][j] 0){ std::queuestd::pairint, int q; q.push({i,j}); cg[i][j] 1; bool is 1; while(!q.empty()){ auto[x,y] q.front(); q.pop(); int nx, ny; if(x 0 || x h - 1 || y 0 || y w - 1){ is 0; } for(int k 0 ; k 4; k){ nx x dx[k]; ny y dy[k]; if(nx 0 nx h ny 0 ny w){ if(s[nx][ny] . cg[nx][ny] 0){ q.push({nx,ny}); cg[nx][ny] 1; } } } } if(is 1){ count; } } } } std::cout count; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); solve(); return 0; }
