专栏首页ypwLake Counting (POJ No.2386)

Lake Counting (POJ No.2386)

题意:有一个M*N的圈子,雨后有积水,然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

思路:这个题目我们很明显可以用并查集来做,但是这个章节是属于DFS,所以我们用DFS来考虑,从任意的W开始,不停的把临接的部分用"."代替。一次DFS后与初始的这个W连接的所有W都被替代转换成“.”。因此直到图中不再存在W为止。总共进行DFS的次数就是答案了。8个方向共对应了8种状态转移,每个格子作为DFS的参数至多被调用一次,所以复杂度为(8 ^ M ^ N)。

#include<bits/stdc++.h>
#define maxn 100003
using namespace std;

char a[maxn][maxn];



void dfs(int x,int y){
     a[x][y] = '.';
	 
	 for(int dx=-1,dx<=1;dx++){
	 	for(int dy=-1;dy<=1;dy++){
	 		int nx = x+dy,ny = y+dy;
	 		if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny] == 'W') dfs(nx,ny);
		 }
	 }
	 return ;	
}

void solve(){
	int res = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j] == 'W'){
				dfs(i,j);
				res++;
			}
		}
	}
	cout<<res<<endl;
}


int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	
	solve();
	
	return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用邻接链表存图 详讲

    在许多图论的题目中,我们首先要存图,之前我已经学习了用邻接矩阵存图 ,但是看许多大佬都是用邻接表存图,觉得还是学习下好!

    用户7727433
  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • Red and Black(DFS 深搜练习)

    There is a rectangular room, covered with square tiles. Each tile is colored eit...

    用户7727433
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • cf547D. Mike and Fish(欧拉回路)

    attack
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • 1048 石子归并

    1048 石子归并 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有n堆石子...

    attack
  • P1197 [JSOI2008]星球大战

    题目描述 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几...

    attack
  • Codeforces Round #521 (Div. 3) D. Cutting Out(二分)

    题目链接:http://codeforces.com/contest/1077/problem/D

    Ch_Zaqdt
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack

扫码关注云+社区

领取腾讯云代金券