P1506

题目

题目描述：

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

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

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

输入格式：

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

接下来 xx 行，每行 yy 个字符，由 * 和 0 组成，表示 oibh 总部的建设图。

输出格式：

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

数据范围与说明：

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

输入输出样例 #1

输入：

1
2
3
4
5
4 5
00000
00*00
0*0*0
00*00

输出：

1
1

输入输出样例 #2

输入：

1
2
3
4
5
6
5 5
*****
*0*0*
**0**
*0*0*
*****

输出：

1
5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[501][501];
int kx[5]={0,1,-1,0,0}; 
int ky[5]={0,0,0,1,-1};
void dfs(int x,int y){
    a[x][y]=1;
    for(int i=1;i<=4;i++){
        int x0=x+kx[i];
        int y0=y+ky[i];
        if(x0>0&&x0<=n&&y0>0&&y0<=m&&a[x0][y0]==0)  dfs(x0,y0);
    }
}
int main(){
    char e;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>e;
            if(e=='*')  a[i][j]=1;
            else    a[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i][1]==0) dfs(i,1);
        if(a[i][m]==0) dfs(i,m); 
    }
    for(int i=1;i<=m;i++){
        if(a[1][i]==0) dfs(1,i);
        if(a[n][i]==0) dfs(n,i); 
    }
    int s=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0)s++;
        }
    }
    cout<<s;
    return 0;
}