Tags: algorithmic misc
Rating:
Initially mark all the cells with `0` as visited.
Loop through all the cells of the grid, when find an unmarked cell, increment the islands count, and find its island and mark all its cells as visited using dfs from the cell. Complexity $\mathcal{O}(n^2)$.
My C++ script
```cpp
#include <bits/stdc++.h>
const int N = 5000;
char grid[N][N];
void dfs(int x, int y) {
if (x < 0 or y < 0 or x >= N or y >= N or grid[x][y] == '0') {
return;
}
grid[x][y] = '0';
dfs(x + 1, y);
dfs(x - 1, y);
dfs(x, y + 1);
dfs(x, y - 1);
}
int main() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
std::cin >> grid[i][j];
}
}
int islands = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '1') {
++islands;
dfs(i, j);
}
}
}
std::cout << "rgbCTF{" << islands << "}" << std::endl;
}
```
Flag
```txt
rgbCTF{119609}
```
