題意#
給你一張建築物的地圖，任務是算出這棟建築物裡面到底有幾個房間。
這張地圖的大小是 \(n \times m\) 的網格，每個格子不是地板就是牆壁。我們可以在地板的格子上自由走動（上下左右四個方向），只要相連的地板就會被視為同一個房間。我們的目標就是找出這張地圖裡總共有多少個獨立的房間。
思路#
這是一道非常經典的圖論入門題，本質上就是在求網格圖上的「連通塊數量」（Connected Components）。
我們可以把地圖看成一張圖，每個地板格子都是一個節點，相鄰的地板之間有邊相連。
最直覺的解法就是遍歷整張地圖。當我們遇到一個還沒有被走過的地板（房間的一部分）時，就將房間的計數器加一，然後從這個格子開始進行深度優先搜尋（DFS）。透過 DFS，我們可以走到這個房間所有連通的其他區域，並把它們都標記為「已走過」，這樣之後就不會重複計算了。
因為每個格子最多被存取一次，時間複雜度為 \(O(n \times m)\)，對於題目給定最大 \(1000 \times 1000\) 的地圖來說，效能上綽綽有餘。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
// 上下左右四個方向的位移陣列
vector<int> mx = {0, 1, 0, -1}, my = {1, 0, -1, 0};
int n, m;
vector<vector<char>> v;
vector<vector<int>> vis;
// DFS 走訪整個相鄰的房間區塊
void dfs(int x, int y) {
vis[x][y] = 1; // 標記為已造訪
for (int i = 0; i < 4; i++) {
int nx = x+mx[i], ny = y+my[i];
// 檢查邊界、是否撞牆，以及有沒有走過
if (nx >= 0 && nx < n && ny >= 0 && ny < m && v[nx][ny] != '#' && !vis[nx][ny]) dfs(nx, ny);
}
}
signed main() { WA();
int cnt = 0; cin >> n >> m;
v.assign(n, vector<char>(m));
vis.assign(n, vector<int>(m));
// 讀入地圖
for (auto &i : v) for (auto &j : i) cin >> j;
// 掃描每格地圖尋找新的房間
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果遇到是地板且還沒造訪過，代表找到新房間
if (v[i][j] == '.' && !vis[i][j]) {
cnt++;
dfs(i, j); // 把整個房間探索完並標記
}
}
}
cout << cnt << '\n';
}
