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


http://www.cnblogs.com/EdwardLiu/p/6562772.html
数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     }
[hihoCoder] 岛屿 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
给你一张某一海域卫星照片,你需要统计:
1. 照片中海岛的数目
2. 照片中面积不同的海岛数目
3. 照片中形状不同的海盗数目

其中海域的照片如下,"."表示海洋,"#"表示陆地。在"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。
.####..  
.....#.  
####.#.  
.....#.  
..##.#.  

输入

第一行包含两个人整数:N 和 M,(1 ≤ NM ≤ 50),表示照片的行数和列数。
以下一个 N * M 的矩阵,表示表示海域的照片。

输出

输出3个整数,依次是照片中海岛的数目、面积不同的海岛数目和形状不同的海岛数目。
上图所示的照片中一共有4座岛屿;其中3座面积为4,一座面积为2,所以不同面积的岛屿数目是2;有两座形状都是"####",所以形状不同的岛屿数目为3。
样例输入
5 7
.####..  
.....#.  
####.#.  
.....#.  
..##.#.  
样例输出
4 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

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts