# C++ DFS and BFS solutions with detailed explanation

• 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; }
``````

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