LC 200 Number of Islands

问题描述

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

参考答案

 1 class Solution {
 2 public:
 3     void foo(vector<vector <char>> &grid,int i, int j){
 4         if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size()) return ;
 5         if(grid[i][j] == '0' ) return; //为了递归准备的停止条件
 6         grid[i][j] = '0'; // 为了避免重复，直接将检测过的value归零
 7         foo(grid,i-1,j);
 8         foo(grid,i+1,j);
 9         foo(grid,i,j-1);
10         foo(grid,i,j+1);
11         
12     }
13    
14     int numIslands(vector<vector<char>>& grid) {
15         int counter = 0;
16         for(int i = 0; i<grid.size();i++){
17             for(int j = 0; j<grid[i].size();j++){
18                 if(grid[i][j] == '1'){
19                     counter ++;
20                     foo(grid,i,j);
21                 }
22             }
23         }
24         return counter;
25     }
26 };

额外补充

SRGA

这道题目让我想到了 种子区域生长算法（Seeded Regin Growing Algorithm），参考了一下别人的答案，还真的十分类似。

基本思路是：种下一个种子（遇到的第一个1区域），然后让它生长（递归）。如果是相同区域，就生长（7~10 行），如果不同（4~5行），就停止。

因为区域种子生长是为了，给所有邻接的区域标记label，从而更好识别图象。但这里不需要label，只需要counter。

防止重复

由初始点位，开始生长，由于递归规则相同，所以初始点位也会进入递归，为了防止重复，只要被接触的区域，全部重新赋值为0。（6行）

的确是一个很聪明的做法。