Depth First Search Algorithm! Time Complexity: $O(M * N)$
#include <iostream>
#include <vector>
using namespace std;
int m, n;
int dfs(vector<vector<int>>& g, vector<vector<int>>& vis, int x, int y) {
// 西(west) ==》北(NORTH) ==》东(EAST) ==》南(SOUTH)
static constexpr int dirs[][2] {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int areas = 1;
for (int i = 0; i < 4; ++i) {
if (g[y][x] & 1 << i) continue; // wall
int nx = x + dirs[i][0], ny = y + dirs[i][1];
if (vis[ny][nx]) continue; // visited
vis[ny][nx] = 1; // mark as visited
areas += dfs(g, vis, nx, ny);
}
return areas;
}
int main(void) {
scanf("%d %d", &m, &n);
vector<vector<int>> g(m, vector<int>(n, 0));
vector<vector<int>> vis(m, vector<int>(n, 0));
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x) cin >> g[y][x];
int components = 0, max_areas = 0; // components == 连通分量的个数
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x)
if (!vis[y][x]) {
vis[y][x] = 1;
max_areas = max(max_areas, dfs(g, vis, x, y));
++components;
}
cout << components << endl << max_areas << endl;
}