LeetCode 200.岛屿数量

798236606

传送门：https://leetcode-cn.com/problems/number-of-islands/

解：
1.深度优先遍历(C)

1. void DFS(int x, int y, char** grid, int nr, int nc)
   
2. {
   
3.     ++grid[x][y];
   
4. 
   
5.     if (x - 1 >= 0 && grid[x - 1][y] == '1') DFS(x - 1, y, grid, nr, nc);
   
6.     if (x + 1 < nr && grid[x + 1][y] == '1') DFS(x + 1, y, grid, nr, nc);
   
7.     if (y - 1 >= 0 && grid[x][y - 1] == '1') DFS(x, y - 1, grid, nr, nc);
   
8.     if (y + 1 < nc && grid[x][y + 1] == '1') DFS(x, y + 1, grid, nr, nc);
   
9. }
   
10. 
    
11. int numIslands(char** grid, int gridSize, int* gridColSize)
    
12. {
    
13.     if (!grid || !gridSize || !*gridColSize) return 0;
    
14.    
    
15.     int num = 0;
    
16.     for (int i = 0; i < gridSize; ++i)
    
17.         for (int j = 0; j < *gridColSize; ++j)
    
18.             if (grid[i][j] == '1' && ++num)
    
19.                 DFS(i, j, grid, gridSize, *gridColSize);              
    
20.    
    
21.     return num;
    
22. }

复制代码

2.广度优先遍历(C++)

1. class Solution {
   
2. public:      
   
3.     void BFS(int x, int y, vector< vector<char> > &grid, int nr, int nc)
   
4.     {
   
5.         queue< pair<int, int> > q;
   
6. 
   
7.         q.push({x, y});
   
8.         while (!q.empty())
   
9.         {
   
10.             x = q.front().first, y = q.front().second;
    
11.             q.pop();
    
12.             
    
13.             if (x - 1 >= 0 && grid[x - 1][y] == '1' && ++grid[x - 1][y]) q.push({x - 1, y});
    
14.             if (x + 1 < nr && grid[x + 1][y] == '1' && ++grid[x + 1][y]) q.push({x + 1, y});
    
15.             if (y - 1 >= 0 && grid[x][y - 1] == '1' && ++grid[x][y - 1]) q.push({x, y - 1});
    
16.             if (y + 1 < nc && grid[x][y + 1] == '1' && ++grid[x][y + 1]) q.push({x, y + 1});
    
17.         }
    
18.     }
    
19.    
    
20.     int numIslands(vector< vector<char> > &grid)
    
21.     {
    
22.         if (!grid.size()) return 0;
    
23.         
    
24.         int nr = grid.size(), nc = grid[0].size(), num = 0;
    
25.         for (int i = 0; i < nr; ++i)
    
26.             for (int j = 0; j < nc; ++j)
    
27.                 if (grid[i][j] == '1' && ++num)
    
28.                     BFS(i, j, grid, nr, nc);
    
29.         
    
30.         return num;
    
31.     }
    
32. };

复制代码