-
Notifications
You must be signed in to change notification settings - Fork 0
/
ccc03s3.cpp
41 lines (39 loc) · 1.07 KB
/
ccc03s3.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
char m[26][26];
vector<int> room;
int area = 0, wood = 0, r = 0, c = 0;
void flood(int x, int y){
area++;
m[x][y] = 'I'; //marks as visited
if (x-1 >= 1 && m[x-1][y] == '.') flood(x-1, y);
if (y-1 >= 1 && m[x][y-1] == '.') flood(x, y-1);
if (x+1 <= r && m[x+1][y] == '.') flood(x+1, y);
if (y+1 <= c && m[x][y+1] == '.') flood(x, y+1);
}
int main(){
cin >> wood >> r >> c;
for (int i = 1; i <= r; i++){
for (int j = 1; j <= c; j++){
cin >> m[i][j];
}
}
for (int i = 1; i <= r; i++){
for (int j = 1; j <= c; j++){
if (m[i][j] == '.'){
area = 0;
flood(i, j);
room.push_back(area);
}
}
}
int ans = 0;
sort(room.begin(), room.end(), greater<int>());
for (auto i = room.begin(); i != room.end() && wood >= *i; i++){
wood -= *i;
ans++;
}
cout << ans << (ans == 1? " room, ": " rooms, ");
cout << wood << " square metre(s) left over\n";
return 0;
}