搜寻：zoj 2165 || poj 1979 Red and Black(BFS)

搜索：zoj 2165 || poj 1979 Red and Black(BFS)

[转]http://blog.****.net/zxy_snow/article/details/6157112

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
queue<int> q;
int n,m,ans,flag[22][22];
char map[22][22];
int dir[8] = {1,0,0,1,-1,0,0,-1};
void BFS()
{
	int i,a,b,x,y;
	while( !q.empty() )
	{
		x = q.front(); q.pop();
		y = q.front(); q.pop();
		for(i=0; i<8; i+=2)
		{
			a = x + dir[i];
			b = y + dir[i+1];
			if( a >= 0 && a < m && b >= 0 && b < n )
				if( !flag[a][b] && map[a][b] == '.' )
				{
					flag[a][b] = 1;
					ans++;
					q.push(a);
					q.push(b);
				}
		}
	}
}
int main()
{
	int i,j;
	while( scanf("%d%d",&n,&m) && ( n || m ) )
	{
		memset(flag,0,sizeof(flag));
		getchar();
		for(i=0; i<m; i++)
			gets(map[i]);
		for(i=0; i<m; i++)
			for(j=0; j<n; j++)
				if( map[i][j] == '@' )
				{
					map[i][j] = '.';
					goto next;
				}
		next:;
		flag[i][j] = 1;
		ans = 1;
		q.push(i);
		q.push(j);
		BFS();
		printf("%d/n",ans);
	}
return 0;
}