全球变暖 BFS

全球变暖问题描述给定一张 N×N 像素的海域照片其中.表示海洋#表示陆地岛屿定义为上下左右四个方向上连通的陆地组成的区域。全球变暖导致岛屿边缘即与海洋相邻的陆地会被淹没。要求计算有多少岛屿会被完全淹没。输入格式第一行整数 N (1 ≤ N ≤ 1000)接下来 N 行每行 N 个字符表示海域照片输出格式一个整数表示会被完全淹没的岛屿数量示例输入7 ....... .##.... .##.... ....... .##... ####... .###... .......输出1运行限制最大运行时间1s最大运行内存256M解题思路1️⃣ 遍历整个地图2️⃣ 遇到一个没访问过的 # 用 BFS / DFS 找出这一整座岛3️⃣ 在搜索这座岛时1.统计总格子数 total2.统计“挨着海水的格子数” flood4️⃣ 搜完一整座岛后判断如果 total flood 说明所有点都在边缘 这座岛会被完全淹没 ✅5️⃣ 统计这样的岛数量#includebits/stdc.husingnamespacestd;intn;vectorstringg;vectorvectorboolvis;intdx[4]{1,-1,0,0};intdy[4]{0,0,1,-1};voidbfs(intsx,intsy,inttotal,intflood){queuepairint,intq;q.push({sx,sy});vis[sx][sy]true;while(!q.empty()){auto[x,y]q.front();q.pop();total;boolisFloodfalse;for(intd0;d4;d){intnxxdx[d];intnyydy[d];if(nx0||nxn||ny0||nyn)continue;if(g[nx][ny].){isFloodtrue;}if(g[nx][ny]#!vis[nx][ny]){vis[nx][ny]true;q.push({nx,ny});}}if(isFlood)flood;}}intmain(){cinn;g.resize(n);for(inti0;in;i){cing[i];}vis.assign(n,vectorbool(n,false));intans0;for(inti0;in;i){for(intj0;jn;j){if(g[i][j]#!vis[i][j]){inttotal0,flood0;bfs(i,j,total,flood);if(totalflood){ans;}}}}coutansendl;return0;}