当前位置: 代码迷 >> 综合 >> HDU 1241 Oil Deposits (DFS 八方向)
  详细解决方案

HDU 1241 Oil Deposits (DFS 八方向)

热度:22   发布时间:2023-12-05 06:40:25.0

//杭电1241

//题意自己看,不会度娘

#include <stdio.h>

#include <math.h>
#include <string.h>
int n,m,flag[105][105],num;
char cmp[105][105];
int spx[]={0,1,0,-1,1,1,-1,-1};
int spy[]={1,0,-1,0,-1,1,1,-1};//八个方向
bool check(int x,int y)
{
if(x<0||y<0||x>=n||y>=m)
return false;
else
return true;
}//检查是否超出边界
void DFS(int x,int y)
{
if(!check(x,y))//如果超出则返回
return ;
flag[x][y]=1;//未超出则设为1后往下走
for(int i=0;i<8;++i)
{
int nx=x+spx[i];
int ny=y+spy[i];//八个方向
if(cmp[nx][ny]=='@'&&flag[nx][ny]==0)//八个方向里有油井则继续向下搜索
DFS(nx,ny);
}
}
int main(int argc, char *argv[])
{
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
for(int i=0;i<n;++i)
scanf("%s",cmp[i]);
num=0;
memset(flag,0,sizeof(flag));
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(!flag[i][j]&&cmp[i][j]=='@')//如果是油井且没走过
{
num++;//油井数量加一
DFS(i,j);//开始搜这个油井
}
}
}
printf("%d\n",num);
}
return 0;

}

//题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1241

//Start-ZJ