LeetCode200。島の数--c ++ dfsソリューション

Leetcode 200 Number Islands C Dfs Solution

---

LeetCodeタイトル列： LeetCodeソリューション
私が行ったすべてのLeetCodeトピックはこの列にあり、そのほとんどにJavaおよびPythonソリューションがあります。

---

「1」（陸）と「0」（水）の2Dグリッドマップが与えられた場合、島の数を数えます。島は水に囲まれ、隣接する土地を水平または垂直につなぐことで形成されます。グリッドの4つのエッジすべてがすべて水に囲まれていると想定できます。

例1：

Input: 11110 11010 11000 00000 Output: 1

例2：

Input: 11000 11000 00100 00011 Output: 3

---

c ++ dfsソリューション

class Solution { public: int numIslands(vector<vector<char>>& grid) { int nr = grid.size() if(nr <= 0) { return 0 } int nc = grid[0].size() int num_islands = 0 for(int r = 0 r < nr r++) { for(int c = 0 c < nc c++) { if(grid[r][c] == '1') { num_islands++ dfs(grid,r,c) } } } return num_islands } private: void dfs(vector<vector<char>>& grid, int r, int c) { int nr = grid.size() int nc = grid[0].size() grid[r][c] = '0' //Apply Depth first search coming from all directions if(r-1 >=0 && grid[r-1][c] == '1') { dfs(grid,r-1,c) } if(r+1 < nr && grid[r+1][c] == '1') { dfs(grid,r+1,c) } if(c-1 >= 0 && grid[r][c-1] == '1') { dfs(grid,r,c-1) } if(c+1 < nc && grid[r][c+1] == '1') { dfs(grid,r,c+1) } } }