Sunday, June 12, 2016

Count Unique Island - [hihoCoder] 岛屿 解题报告

http://www.cnblogs.com/EdwardLiu/p/6562772.html
```数unique island, 比如

110000

110001

001101

101100

100000

``` 4     public int countIsland(int[][] grid) {
5         HashSet<String> set = new HashSet<String>();
6
7         for (int i=0; i<grid.length; i++) {
8             for (int j=0; j<grid[0].length; j++) {
9                 if (grid[i][j] != 1) continue;
10                 StringBuilder path = new StringBuilder();
11                 dfs(grid, i, j, path.append('s')); //start
13             }
14         }
15
16         for(String str : set) {
17             System.out.println(str);
18         }
19
20         return set.size();
21     }
22
23     public void dfs(int[][] grid, int i, int j, StringBuilder sb) {
24         grid[i][j] = 2;
25         //up
26         if (i>=1 && grid[i-1][j]==1) dfs(grid, i-1, j, sb.append('u'));
27         //right
28         if (j<grid[0].length-1 && grid[i][j+1]==1) dfs(grid, i, j+1, sb.append('r'));
29         //down
30         if (i<grid.length-1 && grid[i+1][j]==1) dfs(grid, i+1, j, sb.append('d'));
31         //left
32         if (j>=1 && grid[i][j-1]==1) dfs(grid, i, j-1, sb.append('l'));
33     }```
[hihoCoder] 岛屿 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET

1. 照片中海岛的数目
2. 照片中面积不同的海岛数目
3. 照片中形状不同的海盗数目

```.####..
.....#.
####.#.
.....#.
..##.#.  ```

输出

```5 7
.####..
.....#.
####.#.
.....#.
..##.#.  ```

`4 2 3`

```int M, N, num = 0;
vector<vector<char> > map;
set<int> area;
set<set<int> > shape;

void DFS(pair<int, int> curPos, pair<int, int> oriPos, set<int>& st)
{
int y=curPos.first, x=curPos.second, oy=oriPos.first, ox=oriPos.second;
if(y>=N || y<0 || x<0 || x>=M || map[y][x]!='#') return;
st.insert(y*M+x - oy*M-ox);
map[y][x] = '.';
DFS(make_pair(y+1, x),oriPos, st);
DFS(make_pair(y-1, x),oriPos, st);
DFS(make_pair(y, x+1),oriPos, st);
DFS(make_pair(y, x-1),oriPos, st);
}

int main()
{
cin >> N >> M;
for(int i = 0; i < N; i++)
{
vector<char> vec;
char ch;
for(int j =0; j < M; j++)
{
cin>> ch;
vec.push_back(ch);
}
map.push_back(vec);
}
for(int i = 0; i < N; i++)
for(int j =0; j < M; j++)
if(map[i][j] == '#')
{
set<int> st{0};
DFS(make_pair(i, j),make_pair(i, j), st);
area.insert((int)st.size());
shape.insert(st);
num++;
}
cout << num << " " << area.size() << " " << shape.size() << endl;
return 0;
}```