【題解】CSES - Counting Rooms

題目連結

題目大意

給定一張大小為 $n \times m$ 的地圖，地圖上有地板和牆壁。地板和地板之間若相連則形成一個房間，問有幾個房間？

• $1 \leq n, m \leq 10^3$

題解

我們對每個格子逐一檢查。每當我們遇到新的地板，把房間數量 $+1$，並往外檢查他還連通到哪些地板，把這些位置都塗成牆壁。往外檢查的部分可以用 BFS 或是 DFS 時做 (厲害一點甚至可以用並查集)。底下的程式碼是用 DFS 實作。

#include <bits/stdc++.h>
using namespace std;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<string> grid(n);
	for(int i = 0; i < n; i++) {
		cin >> grid[i];
	}
	auto dfs = [&](auto dfs, int i, int j) -> void {
		grid[i][j] = '#';
		for(int dir = 0; dir < 4; dir++) {
			int ni = i + dx[dir];
			int nj = j + dy[dir];
			if(ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '.') {
				dfs(dfs, ni, nj);
			}
		}
	};
	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(grid[i][j] == '.') {
				dfs(dfs, i, j);
				ans++;
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Counting Rooms