#1310 : 岛屿
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给你一张某一海域卫星照片，你需要统计：
1. 照片中海岛的数目
2. 照片中面积不同的海岛数目
3. 照片中形状不同的海盗数目
其中海域的照片如下，"."表示海洋，"#"表示陆地。在"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。
.####..
.....#.
####.#.
.....#.
..##.#.
上图所示的照片中一共有4座岛屿；其中3座面积为4，一座面积为2，所以不同面积的岛屿数目是2；有两座形状都是"####"，所以形状不同的岛屿数目为3。
输入
第一行包含两个人整数：N 和 M，(1 ≤ N, M ≤ 50)，表示照片的行数和列数。
以下一个 N * M 的矩阵，表示表示海域的照片。
输出
输出3个整数，依次是照片中海岛的数目、面积不同的海岛数目和形状不同的海岛数目。
- 样例输入
-
5 7
. # # # # . .
. . . . . # .
# # # # . # .
. . . . . # .
. . # # . # . - 样例输出
-
4 2 3
思路：（1）求岛屿数目很简单，初始化岛屿数目NumOfIslands为0，遍历所有的点，如果这个点未访问并且为‘#’，则NumOfIslands++,进行DFS搜索，将和这个点属于同一个岛屿的所有为'#'的点标记为已访问。
（2）求解一个岛屿时，计算它的面积，将所有的面积保存下来，去掉重复元素，剩下元素个数即为面积不同的岛屿数。
（3）DFS搜索出所有岛屿，同时把每个岛屿包含的像素坐标也保存起来并按照坐标排序（先根据x从小到大排序，如果x坐标相同，再根据y从小到大排序）。 形状相同的岛屿数目我们可以通过逐一比较岛屿的每一个像素得到。当我们比较岛屿x和岛屿y时，如果每对像素的坐标差都相同，那么x和y的形状就是相同的。（首先如果两个岛屿的面积数不同，形状肯定不同，再根据岛屿x的第i(1 <= i <= 面积-1)个坐标与其第一个坐标的坐标差 ?= 岛屿y的第i个坐标与其第一个坐标的坐标差，如果有一个不相等，则形状不同）。
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std; int N, M;//N为行数，M为列数
char map[][];//存储字符矩阵
bool visit[][];//作为标记的数组 int dx[] = {-, , , };//方向数组，为了优化dfs代码
int dy[] = {, , , -};
int area = ; int NumOfIslands = , NODAI = , NODCI;//最终NumOfIslands表示岛屿数，NODAI表示不同面积的岛屿数，
//计算过程中NumOfIslands也作为某个岛屿的编号，岛屿编号从0开始 struct position {
int x;
int y;
}; int num[];//num[i]存储了编号i岛屿的面积大小 struct position a[][];//表示最多有300个岛屿，每个岛屿最大面积为300即对应300个坐标 bool flag[]; bool cmp(struct position a, struct position b){
if(a.x != b.x)
return a.x < b.x;
else
return a.y < b.y;
} int isSame(struct position *c, struct position *d, int x, int y){//判断两个岛屿形状是否相同
int flag = ;
if(num[x] != num[y])
return ;
for(int i = ; i < num[x]; i++){
if(((c[i].x - c[].x) == (d[i].x - d[].x))&& ((c[i].y - c[].y)== (d[i].y - d[].y)))
continue;
else {
flag = ;
break;
}
}
return flag;
} void dfs(int x, int y){
a[NumOfIslands][area].x = x;//保存第NumOfIslands个岛屿第area个坐标x的值
a[NumOfIslands][area].y = y;
area++;//面积数加1
visit[x][y] = ;//标记坐标（x,y）为已访问
for(int i = ; i < ; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= && nx < N && ny >= && ny < M && map[nx][ny] == '#' && visit[nx][ny] == )
dfs(nx, ny);
}
} int main(){ set<int> v;
int i, j; cin >> N >> M;
//输入字符矩阵
for(i = ; i < N; i++)
cin >> map[i]; for(i = ; i < N; i++) {
for(j = ; j < M; j++){
if(map[i][j] == '#' && visit[i][j] == ){
area = ;//初始化某个岛屿的面积数为0
dfs(i, j);
num[NumOfIslands] = area;
v.insert(area);
NumOfIslands++;
}
}
} NODAI = v.size();//面积不同的岛屿数 NODCI = NumOfIslands; //对每个岛屿的坐标进行排序，方便比较两个岛屿形状是否相同
for(i = ; i < NumOfIslands; i++){
sort(a[i], a[i] + num[i], cmp);
} //计算形状不同的岛屿数
for(i = ; i < NumOfIslands - ; i++){
if(flag[i] == ){
continue;
}
else {
for(j = i+; j < NumOfIslands; j++) {
if((flag[j] == ) && (isSame(a[i], a[j], i, j))){
flag[j] = ;
NODCI--;
}
}
} } cout << NumOfIslands << " " << NODAI << " " << NODCI << endl;
//system("pause");
return ;
}