Solution for CCC '03 S3 - Floor Plan in C++


May 12, 2020 0.016232 seconds C++
#include <bits/stdc++.h>
using namespace std;

typedef long long LL; 
typedef pair<int, int> pii; 
typedef pair<LL, LL> pll; 
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<pii> vii; 
typedef vector<LL> vl; 
typedef vector<vl> vvl;

int n, l, w;

int verify(int i, int j, int k, vi *rooms){
	
	if(i >= 0 && i < l && j >= 0 && j < w && rooms[i][j] == 0){
		rooms[i][j] = k;
		return 1 + verify(i, j - 1, k, rooms) + verify(i + 1, j, k, rooms) + verify(i - 1, j, k, rooms) + verify(i, j + 1, k, rooms);
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	
	cin >> n >> l >> w; 
	string map[l];
	vi rooms[l];
	
	for(int i = 0; i < l; i++){
		cin >> map[i];
	}
	
	for(int i = 0; i < l; i++){
		for(int j = 0; j < w; j++){
			if(map[i][j] == 'I'){
				rooms[i].push_back(-1);
			}else{
				rooms[i].push_back(0);
			}
		}
	}
	
	int k = 0;
	vi rsizes;
	for (int i = 0 ; i < l; i++)
	    for (int j = 0 ; j < w; j++)
		if (rooms[i][j] == 0)
		{
		    rsizes.push_back(verify(i, j, k + 1, rooms));
		    k++;
		}
	
		sort(rsizes.begin(), rsizes.end());
		stack<int> sizestack;
		
		for(int i = 0; i < k; i++){
			sizestack.push(rsizes[i]);
		}
		
		
		int total = 0;
		int c = 0;
		
		while(sizestack.empty() == false && total + sizestack.top() <= n){
			
			total += sizestack.top();
			sizestack.pop();
			c++;
		} 
		
		if(c == 1){
			cout << c << " room, " << n - total << " square metre(s) left over\n";
		}else{
			cout << c << " rooms, " << n - total << " square metre(s) left over\n";
		}
		
	
	return 0;
}

Editorial


No editorial for this problem. :(

Original Problem


You can view the original page for this problem on the DMOJ.