博客

如果用递归的话，如果图过于大，有栈溢出的危险，所以这里用个栈写法。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cctype>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#define LL __int64
using namespace std;
const int maxn=1001;
int mat[maxn][maxn],vis[maxn][maxn];
int dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};
struct point
{
    int x,y;
    point(int x,int y):x(x),y(y) {}
};
void dfs(int x,int y)
{
    /*if(!mat[x][y]||vis[x][y]) return;

    vis[x][y]=1;
    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);*/
    stack<point> s;
    s.push(point(x,y));
    vis[x][y]=1;
    while(!s.empty())
    {
       point p=s.top();
       s.pop();
       for(int i=0;i<8;i++)
       {
           if(!vis[p.x+dx[i]][p.y+dy[i]]&&mat[p.x+dx[i]][p.y+dy[i]])
           {
               s.push(point(p.x+dx[i],p.y+dy[i]));
               vis[p.x+dx[i]][p.y+dy[i]]=1;
           }
       }

    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        memset(mat,0,sizeof(mat));
        memset(vis,0,sizeof(vis));
      //  for(int i=1;i<=n;i++)
       //     for(int j=1;j<=n;j++)
       //         cin>>mat[i][j];
        for(int i=0;i<n;i++)
        {
            string s;
            cin>>s;
            for(int j=0;j<n;j++)
                mat[i+1][j+1]=s[j]-'0';
        }
        int count=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
        {
            if(!vis[i][j]&&mat[i][j])
            {
                count++;
                dfs(i,j);
            }
        }
        cout<<count<<endl;
    }
    return 0;
}