using namespace std; #include #include class Solution { public: int findIslandPerimeter(vector> &matrix) { int rows = matrix.size(); int cols = matrix[0].size(); vector> visited(rows, vector(cols, false)); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == 1 && !visited[i][j]) // if the cell is land and not visited return islandPerimeterDFS(matrix, visited, i, j); } } return 0; } private: static int islandPerimeterDFS(vector> &matrix, vector> &visited, int x, int y) { if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size()) return 1; // returning 1, since this a boundary cell initiated this DFS call if (matrix[x][y] == 0) return 1; // returning 1, because of the shared side b/w a water and a land cell if (visited[x][y]) return 0; // we have already taken care of this cell visited[x][y] = true; // mark the cell visited int edgeCount = 0; // recursively visit all neighboring cells (horizontally & vertically) edgeCount += islandPerimeterDFS(matrix, visited, x + 1, y); edgeCount += islandPerimeterDFS(matrix, visited, x - 1, y); edgeCount += islandPerimeterDFS(matrix, visited, x, y + 1); edgeCount += islandPerimeterDFS(matrix, visited, x, y - 1); return edgeCount; } }; int main(int argc, char **argv) { Solution sol; vector> vec = vector>{ {1, 1, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}}; cout << sol.findIslandPerimeter(vec) << endl; vec = vector>{ {0, 0, 0, 0}, {0, 1, 0, 0}, {0, 1, 1, 0}, {0, 1, 1, 0}, {0, 1, 0, 0}}; cout << sol.findIslandPerimeter(vec) << endl; return 0; };