200. Number of Islands

我想我大概能理解這為什麼能拿到那麼多讚數, 有趣又不失寓意

我們要在一堆水中, 看連結的陸地個數, 我們去維護一張表, 當遇到1時, 就開始往他四周一直四散, 並且經過就記錄起來, 等走到不能再走, 我們就做完一塊了, 然後當我們遇到已經被記錄的,就不要理他了, 直到結束

dfs:

class Solution {
public:
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j){
        if(i < 0 || j < 0 || i >= grid.size() || j>= grid[0].size()){
            return;
        }
        if(grid[i][j] == '1' && visited[i][j] == false){
            visited[i][j] = true;
            dfs(grid, visited, i, j -1);//left
            dfs(grid, visited, i, j +1);//right
            dfs(grid, visited, i -1, j);//top
            dfs(grid, visited, i + 1, j);//down
        }
}
int numIslands(vector<vector<char>>& grid) {
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        int res = 0;
        for(int i = 0; i < grid.size();i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(!visited[i][j] && grid[i][j] == '1'){
                    res++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        return res;
    }
};

bfs:

class Solution {
public:
  int numIslands(vector<vector<char>> &grid) {
    vector<vector<bool>> visited(grid.size(),
                                 vector<bool>(grid[0].size(), false));
    int m = grid.size();
    int n = grid[0].size();
    int res = 0;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (visited[i][j] == true || grid[i][j] == '0') {
          continue;
        }
        queue<pair<int, int>> q;
        q.push({i, j});
        res++;
        while (!q.empty()) {
          pair<int, int> cur = q.front();
          q.pop();
          int x = cur.first;
          int y = cur.second;
if (grid[x][y] == '1' && !visited[x][y]) {
            visited[x][y] = true;
            if (x > 0) {
              q.push({x - 1, y});
            }
            if (x < m - 1) {
              q.push({x + 1, y});
            }
            if (y > 0) {
              q.push({x, y - 1});
            }
            if (y < n - 1) {
              q.push({x, y + 1});
            }
          }
        }
      }
    }
    return res;
  }
};