标题：全球变暖
【题目描述】
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【样例输入】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【样例输出】
1
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
思路:并查集问题(可看如下的代码运行图)
#include<stdio.h>
#include<iostream>
#include<string>
#include<set>
using namespace std;
#define NUM 1000
bool fx[NUM][NUM];
int setf[NUM*NUM];
void sam(int num){//淹没判断
bool fk[NUM][NUM];
int i,j;
for(i=0;i<num;i++){
for(j=0;j<num;j++){
if(fx[i][j]){
if(i==0||i==(num-1)||j==0||j==(num-1))
fk[i][j]=0;
else if(fx[i-1][j]==0||fx[i+1][j]==0||fx[i][j-1]==0||fx[i][j+1]==0)
fk[i][j]=0;
else
fk[i][j]=1;
}
else
fx[i][j]=0;
}
}
for(i=0;i<num;i++){
for(j=0;j<num;j++){
fx[i][j]=(fx[i][j]&fk[i][j]);
}
}
}
int par(int a){//获取最祖宗点
while(1){
if(setf[a]!=a){
a=setf[a];
}
else
break;
}
return a;
}
int result(int num){
int i,j;
//查找“祖宗点”
for(i=0;i<num;i++){
for(j=0;j<num;j++){
if(fx[i][j]==1){
if(i!=0&&fx[i-1][j]==1&&setf[(i-1)*num+j]!=i*num+j)
setf[i*num+j]=par((i-1)*num+j);
else if(i!=num-1&&fx[i+1][j]==1&&setf[(i+1)*num+j]!=i*num+j)
setf[i*num+j]=par((i+1)*num+j);
else if(j!=num-1&&fx[i][j+1]==1&&setf[i*num+(j+1)]!=i*num+j)
setf[i*num+j]=par(i*num+(j+1));
else if(j!=0&&fx[i][j-1]==1&&setf[i*num+(j-1)]!=i*num+j)
setf[i*num+j]=par(i*num+(j-1));
else
continue;
}
else
setf[i*num+j]=-1;
}
}
set<int> boot;
//再次查找“祖宗点”，防止差错，并加入集合
for(i=0;i<num;i++){
for(j=0;j<num;j++){
if(setf[i*num+j]!=-1)
setf[i*num+j]=par(setf[i*num+j]);
printf("%d ",setf[i*num+j]);
boot.insert(setf[i*num+j]);
}
printf("\n");
}
printf("\n");
/*
set<int>::iterator it;
//返回集合所有元素 -1代表海 忽略
for(it=boot.begin();it!=boot.end();it++){
printf("%d",*it);
}
*/
return boot.size()-1;
}
int main(){
int num,i,j,result_1,result_2;
char a;
scanf("%d",&num);
while(1){
a=getchar();
if(a=='\n'||a=='\r')
break;
}
for(i=0;i<num;i++){
for(j=0;j<num;j++){
scanf("%c",&a);
if(a=='#')
fx[i][j]=1;
else
fx[i][j]=0;
setf[i*num+j]=i*num+j;
}
scanf("%c",&a);
}
result_1=result(num);//并查集查找初始情况数目
sam(num);
for(i=0;i<num;i++){//并查集复位
for(j=0;j<num;j++){
setf[i*num+j]=i*num+j;
}
}
/*上升一层后的情况
for(i=0;i<num;i++){
for(j=0;j<num;j++){
printf("%d ",fx[i][j]);
}
printf("\n");
}
*/
result_2=result(num);//并查集查找浸后情况数目
printf("%d",result_1-result_2);
return 0;
}
/*样例
7
.......
.##....
.##....
....##.
..####.
...###.
.......
*/
