hiho一下[156周]：島嶼

給你一張某一海域衛星照片，你需要統計：

1. 照片中海島的數目
2. 照片中面積不同的海島數目
3. 照片中形狀不同的海島數目

其中海域的照片如下，”.”表示海洋，”#”表示陸地。在”上下左右”四個方向上連在一起的一片陸地組成一座島嶼。

.####..  
.....#.  
####.#.  
.....#.  
..##.#.  
           

上圖所示的照片中一共有4座島嶼；其中3座面積為4，一座面積為2，是以不同面積的島嶼數目是2；有兩座形狀都是”####”，是以形狀不同的島嶼數目為3。

輸入

第一行包含兩個整數：N 和 M，(1 ≤ N, M ≤ 50)，表示照片的行數和列數。

以下一個 N * M 的矩陣，表示表示海域的照片。

輸出

輸出3個整數，依次是照片中海島的數目、面積不同的海島數目和形狀不同的海島數目。

樣例輸入

.####..  
.....#.  
####.#.  
.....#.  
..##.#.  
樣例輸出
  
           

思路很簡單，直接dfs即可，不過，需要在搜尋的過程中，記錄#的數量，來表示面積，記錄周遊路徑，使用相對位置表示形狀。

參考代碼（很長，很亂，僅供參考，不建議複制粘貼）：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

struct point {//用一個結構體的表示路徑中的點，友善記錄島嶼的形狀
    int x;
    int y;
    point(int m, int n) {
        x = m;
        y = n;
    }
};
struct mycomp//形狀set kind的自動以排序函數
{
    bool operator () (const std::vector<point>& a, const std::vector<point>& b) const
    {
        if (a.size() == b.size()) {
            for (int i = ; i < a.size(); i++) {
                if (a[i].x == b[i].x) {
                    if (a[i].y == b[i].y) {
                        continue;
                    }
                    return a[i].y > b[i].y;
                }
                return a[i].x > b[i].x;
            }
            return false;
        }
        return a.size() > b.size();
    }
};
void dfs(int i, int j, std::vector<std::vector<bool> > &visited, std::vector<std::vector<char> > &grid, int &area, std::vector<point> &points) {//dfs主要實作函數
    int n = grid.size();
    int m = grid[].size();
    if (i <  || i >= n)
        return;
    if (j <  || j >= m)
        return;
    if (visited[i][j] || grid[i][j] == '.')
        return;
    visited[i][j] = true;
    point p(i, j);
    points.push_back(p);
    area++;
    dfs(i - , j, visited, grid, area, points);
    dfs(i + , j, visited, grid, area, points);
    dfs(i, j - , visited, grid, area, points);
    dfs(i, j + , visited, grid, area, points);
}
int main() {
    using namespace std;
    int n, m;
    while (cin >> n >> m) {
        vector<vector<char> > grid(n, vector<char>(m));
        vector<vector<bool> > visited(n, vector<bool>(m, false));
        int islandNums = ;
        set<int> areas;//面積集合，表示不同面積的島嶼個數
        set<vector<point>, mycomp > kinds;//形狀集合，表示不同形狀的島嶼個數
        int area = ;
        for (int i = ; i < n; i++) {
            for (int j = ; j < m; j++) {
                cin >> grid[i][j];
            }
        }
        for (int i = ; i < n; i++) {
            for (int j = ; j < m; j++) {
                if (grid[i][j] == '#' && !visited[i][j]) {
                    vector<point> points;
                    dfs(i, j, visited, grid, area, points);
                    islandNums++;
                    areas.insert(area);
                    area = ;
                    for (int k = points.size() - ; k >= ; k--) {
                        points[k].x -= points[].x;
                        points[k].y -= points[].y;
                    }
                    kinds.insert(points);
                }
            }
        }
        cout << islandNums << " " << areas.size() << " " << kinds.size() << endl;
    }
    return ;
}