HJ158 挡住洪水

题目题解(22)讨论(12)排行简单 通过率30.19% 时间限制1秒 空间限制256M知识点广度优先搜索(BFS)校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述吴铭市近日洪水肆虐洪水从地图外部渗入。市政部门在若干方格上砌起围墙用 * 表示。若某片空地区域不与地图边界四联通上下左右方向则不会被洪水淹没视为安全空地。地图用大小为 x×yx×y 的字符矩阵描述* 表示围墙0 表示空地。所有相互四联通的 0 构成一个区域。请统计所有安全空地格子的数量之和即所有不与边界四联通的 0 的总数。输入描述第一行输入两个整数 x,y(1≦x,y≦500)x,y(1≦x,y≦500)。接下来 xx 行每行 yy 个字符组成围墙建设图仅含 * 与 0。输出描述输出一个整数表示所有安全空地格子的总数。示例1输入2 2 ** **复制输出0#include iostream #include vector #include string #include queue using namespace std; int n, m; vectorstring grid; int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; void bfs(int start_x, int start_y) { if (grid[start_x][start_y] ! 0) { return; } queuepairint, int q; q.push({start_x, start_y}); grid[start_x][start_y] #; while (!q.empty()) { pairint, int curr q.front(); q.pop(); for (int i 0; i 4; i) { int nx curr.first dx[i]; int ny curr.second dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] 0) { grid[nx][ny] #; q.push({nx, ny}); } } } } int main() { cin n m; grid.resize(n); for (int i 0; i n; i) { cin grid[i]; } // 1. 从边界开始淹没所有不安全的 0 区域 for (int j 0; j m; j) { if (grid[0][j] 0) bfs(0, j); if (n 1 grid[n - 1][j] 0) bfs(n - 1, j); } for (int i 1; i n - 1; i) { if (grid[i][0] 0) bfs(i, 0); if (m 1 grid[i][m - 1] 0) bfs(i, m - 1); } // 2. 统计图中剩余的 0 单元格总数 int safe_cells 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 0) { safe_cells; } } } cout safe_cells endl; return 0; }