CSES – Counting Rooms

題目連結

題意

給一個 n * m 的表格。每一格是地板或是牆壁，你可以往上，往右，往左，往下走地板的格子。問表格裡有幾個房間? (看範例輸入會比較容易懂)

解題方法

所謂的找房間其實就是要找這張圖有幾格連通塊，一個連通塊是指裡面的任兩個點都可以走到對方。而我們可以用 bfs / dfs 來找連通塊。每次遇到一個地板，就 dfs 走完他可以走的地方，這樣就是一個房間。我們在對於每個格子 (如果是地板的話) dfs 就可以找到有幾個連通塊。

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[1005][1005];
bool vis[1005][1005];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; //模擬四個方向 上下左右
bool ok(int i, int j){ // 檢查可不可以走
    if(i < 0 || i >= n) return false;
    if(j < 0 || j >= m) return false;
    if(a[i][j] == '#') return false;
    if(vis[i][j]) return false;
    return true;
}
void dfs(int i, int j){
    for(int d = 0;d < 4;d++){
	int ni = i + dx[d], nj = j + dy[d];
	if(ok(ni, nj)) {
	    vis[ni][nj] = true;
	    dfs(ni, nj);
	}
    }
}
int main(){
    cin >> n >> m;
    for(int i = 0;i < n;i++){
	cin >> a[i];
    }	
    int ans = 0;
    for(int i = 0;i < n;i++){
	for(int j = 0;j < m;j++){
	    if(!vis[i][j] && a[i][j] == '.') {
		vis[i][j] = true;
		dfs(i, j);
		ans ++;
	    } 
	}
    }
    cout << ans << '\n';
}