TCO Round1B 500 EllysFigurines

2013-03-02

05:12 |

15x15 以内の白黒ビットマップが与えられる。１回に 1～R 行または 1～C 列分、白にできる。最小何回で全部白にできるか。

全然思いつかない
dp[x][y][w][h] で [x,x+w) x [y,y+h) を白にする最小回数？とか思って書いてみる
バグってるうちに終了
そもそもこれはだめだ（領域を分断すると本来１回で消せても２回以上に分割されちゃうことがある）

あとで
消す行たち(最大2**15 通り)を決めると黒が残ってる列が決まって、それらを左から順に消してけば回数が出る
気が付かなかった。。

↓あとで(accepted in practice room)

class EllysFigurines {
	public:
	int getMoves(vector<string> B, int R, int C) {
		int W=B[0].size();
		int H=B.size();
		int ans = 1<<30;
		REP(bit, 1<<H) {
			int lans=0;
			int rmy[20]={};
			int rest[20]={};
			REP(y, H) {
				if((bit>>y)&1) {
					lans++;
					REP(i, R) if(y+i<H) rmy[y+i]=1;
				}
				if(!rmy[y]) REP(x, W) if(B[y][x]=='X') rest[x]=1;
			}
			REP(x, W) {
				if(rest[x]) {
					lans++;
					x+=C-1;
				}
			}
			ans=min(ans, lans);
		}
		return ans;
	}
};