当前位置：首页 > java >正文

【题解-洛谷】P1506 拯救oibh总部

java 2025/6/23 19:02:44

题目：P1506 拯救oibh总部

题目背景

oibh 总部突然被水淹没了！现在需要你的救援……

题目描述

oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

输入格式

第一行为两个正整数 $x, y$ 。

接下来 $x$ 行，每行 $y$ 个整数，由 * 和 0 组成，表示 oibh 总部的建设图。

输出格式

输出没被水淹没的 oibh 总部的 0 的数量。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

5 5
*****
*0*0*
**0**
*0*0*
*****

输出 #2

说明/提示

对于 $100\%$ 的数据， $\le x,y \le 500$ 。

代码

#include<iostream>using namespace std;typedef pair<int, int> PII;
const int Maxx = 500 + 10, Maxy = 500 + 10;int x, y, hh, tt = -1, vis[Maxx][Maxy], sum;
char map[Maxx][Maxy];
PII q[Maxx * Maxy];void init(){hh = 0, tt = -1;
}void insert(int i, int j){q[++ tt] = {i, j};
}void dele(){hh ++;
}bool isempty(){return hh > tt;
}void bfs(int sx, int sy){init();insert(sx, sy);vis[sx][sy] = 1;map[sx][sy] = '*';int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while(!isempty()){auto t = q[hh];dele();for(int i = 0; i < 4; i ++){int newx = t.first + dx[i], newy = t.second + dy[i];if(newx >= 0 && newx < x && newy >= 0 && newy < y && map[newx][newy] == '0' && !vis[newx][newy]){insert(newx, newy);vis[newx][newy] = 1;map[newx][newy] = '*';}}}
}int main(){scanf("%d%d", &x, &y);for(int i = 0; i < x; i ++){scanf("%s", map[i]);}for(int i = 0; i < x; i ++){if(map[i][0] == '0' && !vis[i][0]){ // 第一列bfs(i, 0);}if(map[i][y - 1] == '0' && !vis[i][y - 1]){ // 最后一列bfs(i, y - 1);}}for(int j = 0; j < y; j ++){if(map[0][j] == '0' && !vis[0][j]){ // 第一行bfs(0, j);}if(map[x - 1][j] == '0' && !vis[x - 1][j]){ // 最后一行bfs(x - 1, j);}}for(int i = 0; i < x; i ++){for(int j = 0; j < y; j ++){if(map[i][j] == '0'){sum ++;}}}printf("%d", sum);return 0;
}