UVa572——Oil Deposits——简单

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits.

GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides

the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to

determine whether or not the plot contains oil.

A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the

same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to

determine how many different oil deposits are contained in a grid.

题目说明

算法竞赛入门经典上关于图和DFS的一道入门题。可通过这道题开始学习有关最短路、迷宫，贪心之类的算法。

#include <stdio.h>
char a[103][103];
int b[103][103]={0};
int n,m,cnt=0;
void dfs(int x,int y)
{
	int i,j;
				a[x][y]='.';
		for(i=-1;i<=1;i++)
		for(j=-1;j<=1;j++)
		{
			if((x+i<n&&y+j<m&&x+i>0&&y+i>0)&&a[x+i][y+j]=='@')
			{
				a[x+i][y+j]='.';
				dfs(x+i,y+j);
			}
		}
	}

int main()
{
	int i,j;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=0;i<n;i++)
		{
			scanf("%s",&a[i]);
		}
		
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				if(a[i][j]=='@')
				{
					dfs(i,j);
					cnt++;
				}
			}
		}
		printf("%d\n",cnt);
	}
} 
           

PS ：本博客属于中国石油大学胜利学院ACM协会所有！

By：朱天宇