hihocoder 1310 岛屿

#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个坐标与其第一个坐标的坐标差，如果有一个不相等，则形状不同）。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <set>
  4 #include <vector>
  5 #include <algorithm>
  6 using namespace std;
  7 
  8 int N, M;//N为行数，M为列数
  9 char map[55][55];//存储字符矩阵
 10 bool visit[55][55];//作为标记的数组
 11 
 12 int dx[4] = {-1, 0, 1, 0};//方向数组，为了优化dfs代码
 13 int dy[4] = {0, 1, 0, -1};
 14 int area = 0;
 15 
 16 int NumOfIslands = 0, NODAI = 0, NODCI;//最终NumOfIslands表示岛屿数，NODAI表示不同面积的岛屿数，
 17 //计算过程中NumOfIslands也作为某个岛屿的编号，岛屿编号从0开始
 18 
 19 struct position {
 20     int x;
 21     int y;
 22 };
 23 
 24 int num[300];//num[i]存储了编号i岛屿的面积大小
 25 
 26 struct position a[300][300];//表示最多有300个岛屿，每个岛屿最大面积为300即对应300个坐标
 27 
 28 
 29 bool flag[300];
 30 
 31 bool cmp(struct position a, struct position b){
 32     if(a.x != b.x)
 33         return a.x < b.x;
 34     else 
 35         return a.y < b.y;
 36 }
 37 
 38 int isSame(struct position *c, struct position *d, int x, int y){//判断两个岛屿形状是否相同
 39     int flag = 1;
 40     if(num[x] != num[y])
 41         return 0;
 42     for(int i = 1; i < num[x]; i++){
 43         if(((c[i].x - c[0].x) == (d[i].x - d[0].x))&& ((c[i].y - c[0].y)== (d[i].y - d[0].y)))
 44             continue;
 45         else {
 46             flag = 0;
 47             break;
 48         }
 49     }
 50     return flag;
 51 }
 52 
 53 void dfs(int x, int y){
 54     a[NumOfIslands][area].x = x;//保存第NumOfIslands个岛屿第area个坐标x的值
 55     a[NumOfIslands][area].y = y;
 56     area++;//面积数加1
 57     visit[x][y] = 1;//标记坐标（x,y）为已访问
 58     for(int i = 0; i < 4; i++){
 59         int nx = x + dx[i];
 60         int ny = y + dy[i];
 61         if(nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] == '#' && visit[nx][ny] == 0)
 62             dfs(nx, ny);
 63     }
 64 }
 65 
 66 int main(){
 67     
 68     set<int> v;
 69     int i, j;
 70     
 71     cin >> N >> M;
 72     //输入字符矩阵 
 73     for(i = 0; i < N; i++)
 74         cin >> map[i];
 75         
 76     for(i = 0; i < N; i++) {
 77         for(j = 0; j < M; j++){
 78             if(map[i][j] == '#' && visit[i][j] == 0){
 79                 area = 0;//初始化某个岛屿的面积数为0
 80                 dfs(i, j);
 81                 num[NumOfIslands] = area;
 82                 v.insert(area);
 83                 NumOfIslands++;
 84             }
 85         }
 86     }
 87 
 88     NODAI = v.size();//面积不同的岛屿数
 89 
 90     NODCI = NumOfIslands;
 91 
 92     //对每个岛屿的坐标进行排序，方便比较两个岛屿形状是否相同
 93     for(i = 0; i < NumOfIslands; i++){
 94         sort(a[i], a[i] + num[i], cmp);
 95     }
 96 
 97     //计算形状不同的岛屿数
 98     for(i = 0; i < NumOfIslands - 1; i++){
 99         if(flag[i] == 1){
100             continue;
101         }
102         else {
103             for(j = i+1; j < NumOfIslands; j++) {
104                 if((flag[j] == 0) && (isSame(a[i], a[j], i, j))){
105                     flag[j] = 1;
106                     NODCI--;
107                 }
108             }
109         }
110             
111     }
112 
113     cout << NumOfIslands << " " << NODAI << " " << NODCI << endl;
114     //system("pause");
115     return 0;
116 }