1. 题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=1241
2. 题目大意：给出一块方格，若方格为@代表有油田，若为*代表没有油田。若某一格油田的水平、垂直、对角线相邻处也有油田，则他们同属于一块油田。输出油田块的个数。
3. 源代码：
#include<iostream>
#include<memory.h>
#include<stdio.h>
using namespace std;
char map[110][110];
int visited[110][110];
int M,N,sum;
int DFS(int x,int y)
{
int i,j;
if(visited[x][y])//如果八个方向全部都已经访问过,则结束搜索
return 0;
else
{
visited[x][y]=1;
if(map[x][y]=='@')
{
//分别对八个方向进行深度搜索
DFS(x-1,y);
DFS(x-1,y+1);
DFS(x,y+1);
DFS(x+1,y+1);
DFS(x+1,y);
DFS(x+1,y-1);
DFS(x,y-1);
DFS(x-1,y-1);
}
}
}
int main()
{
int i,j;
while(cin>>M>>N && (M||N))
{
getchar();
memset(visited,0,sizeof(visited));
//由于此题DFS的方向有八个，分别判断边界条件太麻烦，故可以将油田扩展为(M+2)*(N+2)，将外围一圈的visited设为1方便判断
for(i=0;i<=M+1;i++)
{
visited[i][0]=1;
visited[i][N+1]=1;
}
for(i=0;i<=N+1;i++)
{
visited[0][i]=1;
visited[M+1][i]=1;
}
//输入map数组
for(i=1;i<=M;i++)
for(j=1;j<=N;j++)
cin>>map[i][j];
//通过sum记录进行DFS的次数得到oil deposit的个数
sum=0;
for(i=1;i<=M;i++)
for(j=1;j<=N;j++)
{
if(!visited[i][j] && map[i][j]=='@')
{
sum++;
DFS(i,j);
}
}
cout<<sum<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163041.html
