Coast Length - P1


http://jobs.p1.com/tech/costal.html
The island municipality of Soteholm is required to write a plan of action for their work with emission of greenhouse gases. They realize that a natural first step is to decide whether they are for or against global warming. For this purpose they have read the IPCC report on climate change and found out that the largest effect on their municipality could be the rising sea level.
The residents of Soteholm value their coast highly and therefore want to maximize its total length. For them to be able to make an informed decision on their position in the issue of global warming, you have to help them find out whether their coastal line will shrink or expand if the sea level rises. From height maps they have figured out what parts of their islands will be covered by water, under the different scenarios described in the IPCC report, but they need your help to calculate the length of the coastal lines.


Task

You will be given a map of Soteholm as an N×M grid. Each square in the grid has a side length of 1 km and is either water or land. Your goal is to compute the total length of sea coast of all islands. Sea coast is all borders between land and sea, and sea is any water connected to an edge of the map only through water. Two squares are connected if they share an edge. You may assume that the map is surrounded by sea. Lakes and islands in lakes are not contributing to the sea coast.


Figure 1: 
Gray squares are land and white squares are water. The thick black line is the sea coast. This example corresponds to Sample Input 1.



Input

The first line of the input contains two space separated integers N and M where 1 ≤ N, M ≤ 1000. The following N lines each contain a string of length M consisting of only zeros and ones. Zero means water and one means land.

Output

Output one line with one integer, the total length of the coast in km.

Sample Input 1
 
Sample Output 1

5 6
011110
010110
111000
000010
000000

 
20
看上面的图就大概能明白,就是上图四周是大海包围的,数海岸线的长度,其中中间空的算是湖岸线了,不能算是海岸线,这就是其中的难点。

主要算法要点:
1 以地图的四周,即地图的边沿,如下图黄色部分:

作为收拾搜索点,使用递归搜索,如果是0,代表是海水能渗入的地方,那么就做好标识,我的代码使用const char WATER = '2',标识;沿这样的点能走到的点都标识为WATER,这样就能标识出海水渗透到的格子,并和内湖的格子区分开来了。

2 第1步解决了标识和区分内湖的问题,然后就解决数海岸线的问题了,我们分开两步来数,第一步数最外边的海岸线,第二部数格子之间的海岸线;
即第一步数:

这里应该数作5条海岸线。
第二步数格子之间的海岸线:

这里应该数作30条海岸线,但是由于格子之间的海岸线会数重复,那么实际的海岸线应该是30/2=15条
最终5 + 15 = 20条海岸线。

理解了两个关键算法点之后,再写算法就不难了,只要处理好代码细节问题就好了。
由于这个网站的判断系统对我来说也比较新,故此对一个新系统的输入输出处理和判别系统都需要熟悉以下,故此多调试以下是必然的了。
const int MAX_N = 1001;
char arr[MAX_N][MAX_N];
int n, m;
const char WATER = '2';

inline bool isLegal(int r, int c)
{
 return 0<=r && 0<=c && r<n && c<m;
}

void fillWater(int r, int c)
{
 if (!isLegal(r, c)) return ;
 if (arr[r][c] != '0') return ;

 arr[r][c] = WATER;
 fillWater(r-1, c);
 fillWater(r+1, c);
 fillWater(r, c-1);
 fillWater(r, c+1);
}

int main()
{
 //freopen("in.txt", "r", stdin);
 scanf("%d %d", &n, &m);
 getchar();
 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < m; j++)
  {
   char a = getchar();
   while (a != '0' && a != '1')
   {
    a = getchar();
   }///< handle io crazy problems.
   arr[i][j] = a;
  }
 }
 for (int i = 0; i < n; i++)
 {
  fillWater(i, 0);
  fillWater(i, m-1);
 }
 for (int j = 1; j+1 < m; j++)
 {
  fillWater(0, j);
  fillWater(n-1, j);
 }

 int outEdge = 0, inEdge2 = 0;

 for (int i = 0; i < n; i++)
 {
  if (arr[i][0] != WATER) outEdge++;
  if (arr[i][m-1] != WATER) outEdge++;
 }
 for (int j = 0; j < m; j++)
 {
  if (arr[0][j] != WATER) outEdge++;
  if (arr[n-1][j] != WATER) outEdge++;
 }

 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < m; j++)
  {
   if (arr[i][j] == WATER)
   {
    if (isLegal(i-1, j))
    {
     if (arr[i-1][j] != WATER) inEdge2++;
    }
    if (isLegal(i+1, j))
    {
     if (arr[i+1][j] != WATER) inEdge2++;
    }
    if (isLegal(i, j-1))
    {
     if (arr[i][j-1] != WATER) inEdge2++;
    }
    if (isLegal(i, j+1))
    {
     if (arr[i][j+1] != WATER) inEdge2++;
    }
   }
   else if (arr[i][j] != WATER)
   {
    if (isLegal(i-1, j))
    {
     if (arr[i-1][j] == WATER) inEdge2++;
    }
    if (isLegal(i+1, j))
    {
     if (arr[i+1][j] == WATER) inEdge2++;
    }
    if (isLegal(i, j-1))
    {
     if (arr[i][j-1] == WATER) inEdge2++;
    }
    if (isLegal(i, j+1))
    {
     if (arr[i][j+1] == WATER) inEdge2++;
    }
   }
  }
 }
 printf("%d", outEdge + (inEdge2>>1));
 return 0;
}

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