Description
话说ZY日行一善，终于天可怜见，某日他居然进入了传说中的国家宝藏。这个区域是个N*N
的矩形方块。每个方块可能放置的是宝物或者是不可翻越的障碍。当某个方块放的是宝物时
，如果其上下左右的某个方块放置的亦是宝物时，则两个方块则被认为是互相连通的。ZY想
到所有的宝物都拾走，但单凭他一个人的力量是不行的，此时地也怜见了，从地下冒出这个
矩形方块的地形图，ZY有了这张地图就可以Judge出整个矩形方块被分成了多少个连通块，
哈哈，此时他拿出他心爱的G11，召唤Oi队员来帮他的忙，但到底要叫多少个人来呢？（我
们假设一个人可以占据一个连通块）于是这个光荣的任务就交给你了，ZY和他的Oi队员们今
后能否过上幸福的生活就全看你的了……
的矩形方块。每个方块可能放置的是宝物或者是不可翻越的障碍。当某个方块放的是宝物时
，如果其上下左右的某个方块放置的亦是宝物时，则两个方块则被认为是互相连通的。ZY想
到所有的宝物都拾走，但单凭他一个人的力量是不行的，此时地也怜见了，从地下冒出这个
矩形方块的地形图，ZY有了这张地图就可以Judge出整个矩形方块被分成了多少个连通块，
哈哈，此时他拿出他心爱的G11，召唤Oi队员来帮他的忙，但到底要叫多少个人来呢？（我
们假设一个人可以占据一个连通块）于是这个光荣的任务就交给你了，ZY和他的Oi队员们今
后能否过上幸福的生活就全看你的了……
Input
第一行一个数字N，代表矩形方块的长，N<=1000
接下来的N行N列，代表宝物的分布，其中0代表宝物，1代表障碍。
接下来的N行N列，代表宝物的分布，其中0代表宝物，1代表障碍。
Output
请输出有多少个连通块。
Sample Input
【输入样例1】
3
0 0 0
1 1 1
0 0 0
【输入样例2】
3
0 1 1
0 0 0
1 1 0
Sample Output
【输出样例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;
//特别要注意，这里的father[i]是指编号为i的连通块的父亲是谁，后面判断两个连通块是否同一个连通块的时候，就根据father[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 }