bfs--

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 char a[1010][1010];
 7 int n,k=0;
 8 int dir1[4]={-1,1,0,0};
 9 int dir2[4]={0,0,1,-1};
10 char map[1010][1010];
11 bool vis[1010][1010];
12 int answer[1010];
13 struct node
14 {
15     int x;
16     int y;
17     int step;
18 }now,nextt;
19 void bfs(int x,int y)
20 {
21     queue <node> q;
22     now.x = x;
23     now.y = y;
24     now.step = 1;
25     q.push(now);
26     while(!q.empty())
27     {
28         now = q.front();
29         q.pop();
30         nextt = now;
31     for (int i = 0;i <= 3;i++)
32     {
33          nextt.x = now.x + dir1[i];
34          nextt.y = now.y + dir2[i];
35         if(nextt.x >= 0 && nextt.x < n && nextt.y >=0&&nextt.y<n&&vis[nextt.x][nextt.y] == 0&&a[nextt.x][nextt.y]==‘1‘)
36         {
37             nextt.step = now.step + 1;
38             vis[nextt.x][nextt.y] = 1;
39             q.push(nextt);
40         }
41     }
42 }
43             k++;
44             answer[k]=now.step;
45             return;
46 }
47 int main()
48 {
49     int x=0,st,ed;
50     scanf ("%d",&n);
51     for (int i = 0;i < n;i++)
52     {
53         scanf ("%s",a[i]);
54         for (int j = 0;j <n;j++)
55         {
56         map[i][j]=‘0‘;
57         vis[i][j]=0;
58         if (a[i][j]==‘1‘&&x==0)
59         {
60             st=i;
61             ed=j;
62             map[i][j]=‘1‘;
63             x++;
64         }
65     }
66 }
67     bfs(st,ed);
68     for (int i = 0;i < n;i++)
69     {
70     for (int j = 0;j < n;j++)
71     {
72         if (i!=st&&j!=ed&&a[i][j]==‘1‘&&a[i-1][j]==‘0‘&&a[i][j-1]==‘0‘&&a[i][j+1]==‘0‘)
73         {
74         map[i][j]=‘1‘;
75         bfs(i,j);
76         }
77         }
78     }
79     sort (answer+1,answer+1+k);
80     cout<<k<<endl;
81     for (int i = 1;i <= k;i++)
82     {
83         printf ("%d\n",answer[i]);
84     }
85     return 0;
86 }