题目2 : 岛屿
时间限制: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
思路：
深搜，搜索过的岛屿，置岛屿为x，并用一个area数组记录，搜索到的岛的面积的大小。面积不同的岛屿，通过岛屿的位置，hash出一个值，利用set的去重功能，最后判断sharp数组中有多少个元素。
注意：关于hash的时候，hash取值，我用84的时候re了，，，91AC了，猜测可能素数的效果更好一些。
AC代码：
#include <stdio.h>
#include <set>
using namespace std; char s[][];
int N, M;
int di[] = {, -, , };
int dj[] = {, , , -};
set<int> area, shape; int dfs(int i, int j, int *mini, int *minj, int *maxi, int *maxj) {
if (i < *mini)
*mini = i;
if (i > *maxi)
*maxi = i;
if (j < *minj)
*minj = j;
if (j > *maxj)
*maxj = j;
s[i][j] = 'x';
int a = ;
for (int d = ; d < ; ++d) {
int ni = i + di[d], nj = j + dj[d];
if (s[ni][nj] == '#')
a += dfs(ni, nj, mini, minj, maxi, maxj);
}
return a;
} int mhash(int mini, int minj, int maxi, int maxj) {
int k = , sh = ;
for (int i = mini; i <= maxi; ++i) {
for (int j = minj; j <= maxj; ++j) {
sh = sh * k + s[i][j];
}
k*=;
}
return sh;
} int main() {
scanf("%d%d", &N, &M);
for (int i = ; i < N; ++i)
scanf("%s", s[i + ] + );
int n1 = ;
for (int i = ; i <= N; ++i)
for (int j = ; j <= M; ++j)
if (s[i][j] == '#') {
n1++;
int mini = i, maxi = i, minj = j, maxj = j;
area.insert(dfs(i, j, &mini, &minj, &maxi, &maxj));
shape.insert(mhash(mini, minj, maxi, maxj));
}
printf("%d %d %d", n1, area.size(), shape.size());
return ;
}