hihocoder1310 岛屿
题意:
中文题意
思路:
dfs,面积和数量都很好求,问题在岛屿形状上,感觉让人比较麻烦,用vector保存各个点,只要两个岛之间每个点距离一样就好了,这里的形状的定义比较狭隘,就是平移可得的意思,如果换成可以旋转等变换得到,会比较麻烦感觉。
ac代码:
C++
// daoyu1310.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
int n, m; //1 <= n, m <= 50
char map[51][51]; //store map
int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };
struct island {
int area;
vector<pair<int, int> > shape;
island(int x, int y, int s)
{
shape.push_back(make_pair(x, y));
area = s;
}
};
bool issame(island* a, island* b)
{
if (a->area != b->area) return false;
for (int k = 1; k < a->shape.size(); k++)
{
if (a->shape[k] != b->shape[k]) return false;
}
return true;
}
int count(int i, int j, island* is)
{
if (map[i][j] == '#')
{
map[i][j] = '*'; //represent visited
is->shape.push_back(make_pair(i - is->shape[0].first, j - is->shape[0].second));
}
else
{
return 0;
}
int s = 1;
int nexti, nextj;
for (int k = 0; k < 4; k++)
{
nexti = i + dir[k][0];
nextj = j + dir[k][1];
if (nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && map[nexti][nextj] == '#')
s += count(nexti, nextj, is);
}
return s;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> map[i][j];
vector<island*> res;
set<int> area;
int countshape = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (map[i][j] == '#')
{
island* il = new island(i, j, 1);
il->area = count(i, j, il);
area.insert(il->area);
countshape++;
for (int k = 0; k < res.size(); k++)
{
if (issame(il, res[k]))
{
countshape--;
break;
}
}
res.push_back(il);
}
}
//for (int i = 0; i < res.size(); i++)
//{
// cout << res[i]->area << endl;
// for (int j = 0; j < res[i]->shape.size(); j++)
// {
// cout << res[i]->shape[j].first << " " << res[i]->shape[j].second<< endl;
// }
// cout << endl;
//
//}
//if (issame(res[0],res[2])) cout << "hello" << endl;
cout << res.size() << " " << area.size() << " " << countshape << endl;
return 0;
}