zoj 1709 Oil Deposits

zoj 1709 Oil Deposits

/*
深搜应用
遍历每一个
用map记录探测出的油井的位置
没有探测出油井的地方为1
用DFS对每一个油井进行深搜
相连的的标记为1
这样一趟深搜下来连在一块的油井都被标记为1了
用ans记录进行的深搜次数即为要求的油井种类
*/
#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#define N 105
using namespace std;
int m,n;
int map[N][N],dir[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
bool legal(int x,int y)
{if(x>=1&&x<=m&&y>=1&&y<=n) return true;return false;}
void DFS(int x,int y)
{
	int i,sx,sy;
	map[x][y]=1;
	for(i=0;i<8;i++)
	{
		sx=x+dir[i][0];sy=y+dir[i][1];
		if(legal(sx,sy)&&!map[sx][sy])
			DFS(sx,sy);
	}
}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif
 
		int ans,i,j;char ch;
	   while(cin>>m>>n&&m&&n)
		{
			memset(map,0,sizeof(map));
			for(i=1;i<=m;i++)
			{
				for(j=1;j<=n;j++)
				{
					cin>>ch;
					if(ch=='*')
						map[i][j]=1;
				}
			}
			ans=0;
			for(i=1;i<=m;i++)
			{
				for(j=1;j<=n;j++)
				{
					if(!map[i][j])
					{
						DFS(i,j);
						ans++;
					}
				}
			}
			cout<<ans<<endl;
		}
		return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注