C++ DFS and BFS solutions with detailed explanation


  • 0

    The key observation is that every unit length of perimeter is associated with a unique common boundary shared by a land cell and a water cell (or an out-of-bound cell). Therefore, the idea is straightforward:

    • Find a land cell from the grid as the starting point (if no such cell, apparently perimeter will be 0).
    • Search (DFS or BFS) adjacent cells and increment perimeter only if encountering adjacent water or out-of-bound cells; otherwise, continue to search unvisited adjacent land cells and ignore visited land cells.
    • When all land cells are visited, the perimeter calculation is complete as well.

    DFS:

    int islandPerimeter(vector<vector<int>>& g) {
          m = g.size(); if (!m) return res;
          n = g[0].size(); if (!n) return res;
          for (int i = 0; i < m; ++i) 
          for (int j = 0; j < n; ++j) {
              if (!g[i][j]) continue;
              dfs(i, j, g); return res;          
          }
          return res;
        }
        
        void dfs(int i, int j, vector<vector<int>>& g) {
          if (!inbound(i, j) || !g[i][j]) { res++; return; }    
          if (g[i][j] < 0) return;
          g[i][j] = -1;
          for (auto& d:dirs) dfs(i+d.first, j+d.second, g);
        }
    

    BFS:

        int islandPerimeter(vector<vector<int>>& g) {
          m = g.size(); if (!m) return res;
          n = g[0].size(); if (!n) return res;
          for (int i = 0; i < m; ++i) 
          for (int j = 0; j < n; ++j) {
              if (!g[i][j]) continue;
              queue<pair<int, int>> q; q.emplace(i, j); g[i][j] = -1;
              while (!q.empty()) {
                i = q.front().first; j = q.front().second; q.pop();
                for (auto& d:dirs) {
                  int ii = i + d.first, jj = j + d.second;    
                  if (!inbound(ii, jj) || !g[ii][jj]) res++; 
                  else if (g[ii][jj] > 0) q.emplace(ii, jj), g[ii][jj] = -1;
                }
              }
              return res;          
          }
          return res;
        }
    

    Global variables and helper functions:

        int m, n, res = 0; // grid dimensions and res to store result
        vector<pair<int, int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        bool inbound(int i, int j) { return i>=0 && i<m && j>=0 && j<n; }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.