别墅房间 CodeVS原创

时间限制: 1 s 空间限制: 64000 KB 题目等级 : 青铜 Bronze

题目描述 Description

小浣熊松松到他的朋友家别墅去玩，发现他朋友的家非常大，而且布局很奇怪。具体来说，朋友家的别墅可以被看做一个N*M的矩形，有墙壁的地方被标记为’#’，其他地方被标记为’.’。两个格子(a,b)和(c,d)被当做在同一个房间内，当且仅当|a-c|+|b-d|=1。现在松松想知道，有多少个房间。

输入描述 Input Description

第一行包含两个整数，N和M。

接下来N行描述别墅的情况，只包含’*’和’.’。

输出描述 Output Description

输出仅一行，为房间数。

样例输入 Sample Input

3 3

.#.

#.#

.#.

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于90%的数据，1<=N,M<=1000；

对于100%的数据，1<=N,M<=2000。

代码实现：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n,m,ans;
 5 int bh[]={1,0,-1,0},bl[]={0,1,0,-1};
 6 char ch;
 7 bool map[2010][2010];
 8 void dfs(int h,int l){
 9     map[h][l]=1;
10     for(int i=0;i<4;i++){
11         int nh=h+bh[i],nl=l+bl[i];
12         if(!map[nh][nl]&&nh>0&&nh<=n&&nl>0&&nl<=m) dfs(nh,nl);
13     }
14 }
15 int main(){
16     scanf("%d%d",&n,&m);
17     for(int i=1;i<=n;i++)
18     for(int j=1;j<=m;j++){
19         cin>>ch;
20         if(ch=='#') map[i][j]=1;
21     }
22     for(int i=1;i<=n;i++)
23     for(int j=1;j<=m;j++)
24     if(!map[i][j]){ans++;dfs(i,j);}
25     printf("%d
",ans);
26     return 0;
27 }

好消息，我还会打搜索。

题目来源：CODE[VS]