Description
Input
Output
Sample Input
Sample Output
题意：输入两个数字分别代表输入字符的行和列，然后输入一组字符，里面只有@和*，让你求所有的@构成的块，只要@与@之间紧邻的有同行同列同对角线的关系中的一个就是同一块，让你求出所有这种块的个数；当输入0 0时就结束。
分析：题目实质就是求连通块的块树。
思路：每次从有石油的结点出发，用深度优先遍历思想(DFS)，标志结点。每次进行遍历都能标记一个区域，区域的个数就是所求，具体可参考：数据结构基础之图部分的黑白图像部分
#include <cstdio>
#include<cstring>
const int maxz=100+5;
char ch[maxz][maxz];
int m,n,x[maxz][maxz];//该数组用来记路每一个点，防止重复
void dfs(int r,int c,int id)
{
if(r<0||r>=m||c<0||c>=n) return;//"出界"的格子
if(x[r][c]>0||ch[r][c]!='@') return;//不是“@”或者已经访问过的格子
x[r][c]=id;//编号防止同一格子被多次访问
for(int dr=-1;dr<=1;dr++)
for(int dc=-1;dc<=1;dc++)//搜索周围的八个方向
if(dr!=0||dc!=0) dfs(r+dr,c+dc,id);
}
int main()
{
while(scanf("%d%d",&m,&n)==2&&m&&n)
{
for(int i=0;i<m;i++)
scanf("%s",ch[i]);//%s输入字符串
memset(x,0,sizeof(x));//清零
int count=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(x[i][j]==0&&ch[i][j]=='@') dfs(i,j,++count);//满足条件就加一，然后继续遍历
printf("%d
",count);
}
return 0;
}