学步园

/*输入一个n*n的黑白图像，（1代表黑色，0代表白色），任务是统计其中八连块的个数。
如果两个黑格子有公共边或者公共定点，就说他们属于一个八连块。*/


#include<stdio.h>
#include<iostream>
#include<string.h>

using namespace std;
const int maxn =100;//注意
int mat[maxn][maxn],vis[maxn][maxn];//mat[][]是图的数组，vis[][]是访问标记数组，访问过为1，没访问过为0
void dfs(int x,int y)//dfs(depth-first search )深度优先遍历，从一个节点出发，按照某种特定的次序依次访问图中的节点
{
	if(!mat[x][y]||vis[x][y]) return;

	vis [x][y]=1;//标记（x，y）已经被访问过
	dfs(x-1,y-1);dfs(x-1,y);dfs(x-1,y+1);
	dfs(x,y-1);              dfs(x,y+1);
	dfs(x+1,y-1);dfs(x+1,y);dfs(x+1,y+1);
}



int main()
{
    int n;
    FILE *fp;
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    scanf("%d",&n);
    memset(mat,0,sizeof(mat));
    memset(vis,0,sizeof(vis));
    char s[maxn];
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        for(int j=0;j<n;j++)
            mat[i][j]=s[j]-'0';//将图像往中间挪一点，空出一圈白格子。
    }
     int count=0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
    if(!vis[i][j]&&mat[i][j]){count++;dfs(i,j);}//找到没访问过的黑格子
    cout<<count<<endl;
    return 0;
}

/*maxn这个值如果是100就好，但如果是1000的话会，值过大，影响深度遍历函数（已证明对主函数中的第二个二重for循环没有影响，
因为该处的算法复杂度仅仅是O(n^2)），*/