个人技术分享

拯救oibh总部

题目背景

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

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

4 5
00000
00*00
0*0*0
00*00

样例输出 #1

1

样例 #2

样例输入 #2

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

样例输出 #2

5

提示

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

#include<iostream>
#include<cstring>
#include<queue> 
using namespace std;
const int N=510;
typedef pair<int,int> PII;
char g[N][N];
bool st[N][N];
PII q[N*N];
int hh=0,tt=-1;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n,m;

void bfs(int x1,int y1){
	q[++tt]={x1,y1};
	st[x1][y1]=true;
	while(hh<=tt){
		PII t=q[hh++];
		
		for(int i=0;i<4;i++){
			int x2=t.first+dx[i];
			int y2=t.second+dy[i];
		
			if(x2<0||x2>n+1||y2<0||y2>m+1)continue;
			if(st[x2][y2])continue;
			if(g[x2][y2]=='*')continue;
			q[++tt]={x2,y2};
			st[x2][y2]=true;
		}
		
	}
}

int main(){
	cin>>n>>m;

	for(int i=0;i<=N-1;i++)
	 	for(int j=0;j<=N-1;j++)g[i][j]='0';
	 	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cin>>g[i][j];
		
		

		
	
	bfs(0,0);

	int res=0;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)if(g[i][j]=='0'&&!st[i][j])res++;

	cout<<res;
	return 0;
}