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:朱天宇