【題解】Zerojudge a597 - 祖靈被榨乾了!!!!!!!!

題目連結

題目大意

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

• $1 \leq n, m \leq 500$

題解

本題與 CSES - Counting Rooms 大致相同，請參考【題解】CSES - Counting Rooms 這篇文章。本題需要額外紀錄房間的大小，可以在做 DFS 的過程中一起記錄。注意輸入是讀到 EOF 結束。其他實作的細節請參考 code。

#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;
	while(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) -> int {
			int sz = 1;
			grid[i][j] = 'X';
			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] == 'J') {
					sz += dfs(dfs, ni, nj);
				}
			}
			return sz;
		};
		int ans = 0, max_sz = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(grid[i][j] == 'J') {
					int sz = dfs(dfs, i, j);
					ans++;
					max_sz = max(max_sz, sz);
				}
			}
		}
		cout << ans << " " << max_sz << "\n";
	}
	return 0;
}

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

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