HJ159 没挡住洪水

题目题解(10)讨论(10)排行简单 通过率26.80% 时间限制1秒 空间限制256M知识点广度优先搜索(BFS)校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述吴铭市近日洪水肆虐然而市政部门紧急在若干方格上砌起围墙是豆腐渣工程被洪水中的强腐蚀性物质一氧化二氢分解了只剩下了用 # 表示的空地。地图用大小为 N \times N 的字符矩阵描述. 表示已经被洪水淹没的区域# 表示空地。四联通的 # 组成一个区域。聪明睿智的吴铭市防洪抗灾紧急委员会官员在全市防洪抗灾紧急会议上指出在接下来的一天中洪水仍将上涨所有与已经被洪水淹没的区域相邻上下左右方向的空地格子都会被淹没。请计算在此次上涨后吴铭市中将有多少个区域被完全淹没。输入描述第一行输入整数 N(1≦N≦1000)N(1≦N≦1000)。随后 NN 行每行 NN 个字符构成吴铭市的地图只含 . 与 #。已知边界四条边全部为已经被洪水淹没的区域。输出描述输出一个整数表示一天后会完全消失的空地区域数量。示例1输入1 .复制输出0#include iostream #include queue #include vector using namespace std; //四个方向 vectorvectorint direction { {1,0},{0,1},{-1,0},{0,-1} }; int bfs(vectorvectorchar map, pairint,int point) { int rows map.size(); int cols map[0].size(); queuepairint, int q; q.push(point); int xn 0, yn 0; bool all_beside_water true;//是否全与水相邻即是否被完全淹没 while (!q.empty()) { bool beside_water false; auto [x, y] q.front(); map[x][y] *;//已访问过用*标记 q.pop(); for (auto dir : direction) { xn x dir[0]; yn y dir[1]; if (map[xn][yn] .||xn 0 || xn rows || yn 0 || yn cols)//与水相邻 { beside_water true; } if (xn 0 xn rows yn 0 yn colsmap[xn][yn] #)//相邻空地加入队列 { q.push({ xn,yn }); } } if (beside_water false)//只要有一个与水不相邻即不完全与水相邻 all_beside_water false; } if (all_beside_water false)//不完全与水相邻不会被水淹没 return 0; else return 1; } int main() { int n; cin n; vectorvectorchar map(n, vectorchar(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin map[i][j]; } } int count 0; for (int i 0; i n; i) { for (int j 0; j n; j) { if (map[i][j] #)//寻找空地bfs遍历 count bfs(map, { i,j }); } } cout count; }