http://www.cnblogs.com/EdwardLiu/p/6562772.html
[hihoCoder] 岛屿 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
数unique island, 比如 110000 110001 001101 101100 100000 总共两个unique岛,不是四个
方法可以是记录每次新的岛屿搜索的路径,left,right,up,down, 作为标志是否相同的key,存hashset
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 12 set.add(path.toString()); 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 }
- 样例输入
5 7 .####.. .....#. ####.#. .....#. ..##.#.
样例输出4 2 3
给你一张某一海域卫星照片,你需要统计:
1. 照片中海岛的数目
2. 照片中面积不同的海岛数目
3. 照片中形状不同的海盗数目
其中海域的照片如下,"."表示海洋,"#"表示陆地。在"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。
.####.. .....#. ####.#. .....#. ..##.#.
输入
第一行包含两个人整数:N 和 M,(1 ≤ N, M ≤ 50),表示照片的行数和列数。
以下一个 N * M 的矩阵,表示表示海域的照片。
输出
输出3个整数,依次是照片中海岛的数目、面积不同的海岛数目和形状不同的海岛数目。
上图所示的照片中一共有4座岛屿;其中3座面积为4,一座面积为2,所以不同面积的岛屿数目是2;有两座形状都是"####",所以形状不同的岛屿数目为3。
思路: 一个普通的DFS的延伸, 其中岛屿的个数比较容易计算, 就是遍历数组碰到'#'就进行DFS, 并且为了防止再次搜索到这个点, 我们可以搜过之后改变其值. 面积就是每次搜索到的'#'的个数, 也比较容易. 海岛形状这个我们可以保存搜到的海岛的位置, 并且以最初的起点的岛屿为相对值0, 一个位置可以表示成(y*n + x), 这样我们就可以以一个数的形式保存一个位置, 保存的时候都减去起始点的值, 然后将其保存的二叉搜索树中去, 这样可以保持其大小有序. 然后看其不同的个数有多少即可.
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; }Read full article from [hihoCoder] 岛屿 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET