POJ 2386 Lake Counting【BFS】

题意：给出一个矩形，问有多少块连通的W

当找到W的时候，进行广搜，然后将搜过的W变成点，直到不能再搜，进行下一次广搜，最后搜的次数即为水塘的个数

看的PPT里面讲的是种子填充法。

种子填充算法：

从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止对于这一题：先枚举矩阵中的每一个元素，当元素为W的时候，对它进行种子填充(BFS)

种子填充过程：

1）将八个方向的状态分别加进队列

2）如果元素为W,将其改为点

3）用BFS将相邻的点加入队列，直到没有可加入的节点

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int n,m,r;

int dir[8][2]={{-1,1},{0,1},{1,1},{-1,0},{1,0},{-1,-1},{0,-1},{1,-1}};

char map[1000][1000];

void bfs(int x,int y)

{

    queue<int> q;

	q.push(x);q.push(y);

	map[x][y]='.';

	while(!q.empty())

	{

		int  a=q.front();q.pop();

		int  b=q.front();q.pop();

		for(int i=0;i<8;i++)

		{

			int c=a+dir[i][0];

			int d=b+dir[i][1];

			if(c>0&&c<=n&&d>0&&d<=m&&map[c][d]=='W')

			{

				map[c][d]='.';

				q.push(c);q.push(d);

			}

		}

	}

}

int main()

{

	int i,j,ans;

	while(scanf("%d %d",&n,&m)!=EOF)

	{

		ans=0;

		for(i=1;i<=n;i++)

		 for(j=1;j<=m;j++)

			cin>>map[i][j];

				for(i=1;i<=n;i++)

				 for(j=1;j<=m;j++)

					if(map[i][j]=='W') ans++,bfs(i,j);

		printf("%d\n",ans);

	}

}

巴特西

POJ 2386 Lake Counting【BFS】

最新文章

热门文章