SRM 505 Div1 Easy RectangleArea

問題概要

幅W,高さHの長方形が横N本、縦M本の直線により、NM個の小長方形に分割されている。
長方形のうちいくつかの面積がが与えられる。

このとき、全体の長方形の面積を求めるのに、さらに必要な小長方形の面積の情報の個数を求めよ。

制約条件

N,M ≦ 50

方針

y行目x列目の長方形を長方形(y,x)と表す。
長方形(y0,x0),(y1,x0),(y0,x1),(y1,x1)のうち、3つの面積の情報がわかっているとき、
残り一つの面積もわかる。

逆に、ある部分の面積が、今までの情報を使ってどうやってもわからないとき、
その部分の面積の情報は知る必要がある。

したがって、全ての長方形の面積がわかるまで、
わからない部分を貪欲に知る→そこからわかる面積を全部求める
を繰り返せばよいことがわかる。

ソースコード

int h,w;
vs k;

void rec(int y,int x){
	k[y][x]='Y';
	
	rep(i,h)rep(j,w){
		int Y = (k[y][x]=='Y') + (k[y][j]=='Y') + (k[i][x]=='Y') + (k[i][j]=='Y');
		if(Y==3){
			if(k[y][j]=='N')rec(y,j);
			if(k[i][x]=='N')rec(i,x);
			if(k[i][j]=='N')rec(i,j);
		}
	}
}

class RectangleArea {
	public:
	int minimumQueries(vector <string> known) 
	{
		k=known;
		h=k.size(), w=k[0].size();
		
		rep(i,h)rep(j,w)if(k[i][j]=='Y')rec(i,j);
		
		int ans=0;
		rep(i,h)rep(j,w)if(k[i][j]=='N')rec(i,j),ans++;
		return ans;
	}
};