BFS-Lake Counting

发布于:2022-12-31 ⋅ 阅读:(187) ⋅ 点赞:(0)

题目描述:

有一块N×M的土地,雨后积起了水,有水标记为‘W’,干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼?

输入描述

第一行为N,M(1≤N,M≤110)。

下面为N*M的土地示意图。

输出描述

一行,共有的水洼数。

用例输入 1 

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

用例输出 1 

3

代码如下:

#include<bits/stdc++.h>
using namespace std;
int m,n;
char a[120][120];
int dl[10001][3]={};
int xx[8]={-1,1,0,0,-1,-1,1,1};
int yy[8]={0,0,1,-1,1,-1,1,-1};
int bfs(int i,int j){
	dl[1][0]=i;
	dl[1][1]=j;
	a[i][j]='.';
	for(int begin=1,end=1;begin<=end;begin++){
		for(int k=0;k<=7;k++){
			int tx=dl[begin][0]+xx[k];
			int ty=dl[begin][1]+yy[k];
			if(a[tx][ty]=='W'){
				end++;
				dl[end][0]=tx;
				dl[end][1]=ty;
				a[tx][ty]='.';
			}
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	int s=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]=='W'){
				bfs(i,j);
				s++;
			}
		}
	}
	cout<<s;
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到