Monday, April 20, 2015

200 Number of Islands

来源:Leetcode, Google常考题

原帖:https://leetcode.com/problems/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.
思路:找到连通域的数目,典型的bfs, dfs题目。

代码:DFS
 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     void dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int r, int c) {  
         int M = grid.size(), N = grid[0].size();  
         visited[r][c] = true;  
         for (auto o : offset) {  
             int i = r + o.first, j = c + o.second;  
             if (i < 0 || i >= M || j < 0 || j >= N) continue;  
             if (grid[i][j] == '0' || visited[i][j]) continue;  
             dfs(grid, visited, i, j);  
         }  
     }  
   
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     dfs(grid, visited, i,j);  
                 }  
             }  
         }  
         return count;  
     }  
 };  
代码:BFS
 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     queue<pair<int,int>> q;  
                     visited[i][j] = true;  
                     q.push({i,j});  
                     while (!q.empty()) {  
                         auto neigh = q.front(); q.pop();  
                         for (auto o : offset) {  
                             int r = neigh.first + o.first, c = neigh.second + o.second;  
                             if (r < 0 || r >= M || c < 0 || c >= N) continue;  
                             if (visited[r][c] || grid[r][c] == '0') continue;  
                             visited[r][c] = true;  
                             q.push({r,c});  
                         }  
                     }  
                 }  
             }  
         }  
         return count;  
     }  
 };  

No comments:

Post a Comment