<> subject ：

difficulty ： secondary
Give you a ‘1’（ land ） and ‘0’（ water ） Two dimensional mesh composed of , Please calculate the number of islands in the grid .
The island is always surrounded by water , And each island can only be connected by adjacent land in horizontal or vertical direction .
in addition , You can assume that all four sides of the mesh are surrounded by water .

Example 1:
input : 11110 11010 11000 00000
output : 1

Example 2:
input : 11000 11000 00100 00011
output : 3
explain : Each island can only be composed of horizontal and / Or connected by adjacent land in vertical direction .

<> Problem solving ：

Solutions to problems

* Find the island by traversing
* Recurse the entire island found , Simultaneously converted to sea water
* Repeat the above two steps
be careful ： Treatment threshold

code
class Solution { public: int numIslands(vector<vector<char>>& grid) { int count
= 0; for(int i = 0; i < grid.size(); i++){ for(int j = 0; j < grid[0].size(); j
++){ if(grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count; }
void dfs(vector<vector<char>>& grid, int x, int y){ if(grid[x][y] == '0') return
; grid[x][y] = '0'; if(x > 0) dfs(grid, x - 1, y); if(x < grid.size()-1) dfs(
grid, x + 1, y); if(y > 0) dfs(grid, x, y - 1); if(y < grid[0].size()-1)dfs(grid
, x, y + 1); } };

Technology
Daily Recommendation
views 7