【输入样例1】
3
0 0 0
1 1 1
0 0 0
【输入样例2】
3
0 1 1
0 0 0
1 1 0
【输出样例1】
2
【输出样例2】
1
sol：此题粗看很简单，用bfs或dfs搜索就好了，但注意此题的内存限制是3M，因此无法存储整张图，从而无法进行遍历点的操作了。
但我们还是可以存储2行图的，于是可以对当前点[i,j]进行分类讨论。若当前点是宝藏，则看与上方和左边点是否连通，有以下几种情况:
1.上方点和左边点都不是宝藏，则当前点独立成一个连通块，连通块数量增加一个；
2.上方点不是宝藏，左边点是宝藏，则当前点与左边点构成一个连通块；
3.上方点是宝藏，左边点不是宝藏，则当前点与上方点构成一个连通块；
4.上方点和左边点都是宝藏，则通过当前点进行连通，这时要看上方点和左边点是否属同一个连通块，如果不是，则连通后连通块数量减少一个。
当然，如果当前点不是宝藏，就不用管它了。
此题可用并查集实现。
另外该题的数据，如果出现极端情况，如点是01相间给出，则该方法仍不能实现。
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int k,t,p,q,n,tot,ans;
5 int father[50010];
6 bool mapp[2][50010];
7 int f[2][50010];
8 int find(int x)
9 {
10 if(x!=father[x])
11 father[x]=find(father[x]);
12 return father[x];
13 }
14 int main()
15 {
16 scanf("%d",&n);
17 for(int i=1;i<=50000;i++)
18 father[i]=i;
19 t=0;
20 for(int i=1;i<=n;i++)//处理n行矩形方块
21 {
22 t^=1;
23 for(int j=1;j<=n;j++)//读入每行的j列方块信息
24 {
25 scanf("%d",&k);
26 if(k==0)
27 mapp[t][j]=true;
28 else
29 mapp[t][j]=false;
30 }
31 for(int j=1;j<=n;j++)
32 {
33 if(mapp[t][j])//如果当前方块是宝藏
34 {
35 if(!mapp[t^1][j]&&!mapp[t][j-1])//其上方和左边方块不是宝藏
36 {
37 tot++;//连通块的编号
38 ans++;//连通块数量
39 f[t][j]=tot;//当前t行j列单独成为一个连通块
40 }
41 else
42 if(!mapp[t^1][j]&&mapp[t][j-1])//上方不是宝藏，左边是
43 f[t][j]=f[t][j-1];//当前方块与左边成为一个连通块
44 else
45 if(mapp[t^1][j]&&!mapp[t][j-1])//上方是宝藏，左边不是
46 f[t][j]=f[t^1][j];//当前方块与上方成为一个连通块
47 else//左边和上方都是宝藏，则通过当前方块连通
48 {
49 f[t][j]=f[t^1][j];
50 p=find(f[t^1][j]);
51 q=find(f[t][j-1]);
52 if(p!=q)//看上方方块和左边方块是否是同一个连通块，若不是
53 {
54 father[p]=min(p,q);//连通
55 father[q]=min(p,q);
56 ans--;//连通块数量-1
57 }
58 }
59 }
60 }
61 }
62 printf("%d",ans);
63 }
原文：https://www.cnblogs.com/cutepota/p/12462903.html