Codeforces #222 Div1. A. Maze

年末最後のCodeforces通常ラウンドは、ABC解いて自己ベスト更新と好調な終わり方でした。
CはMLEしたりHackを凡ミスしたりとドタバタしたけどね。A,Bがすんなりいってよかった。
http://codeforces.com/contest/377/problem/A

問題

HxWのグリッドが与えられ、一部マスは移動不可能となっている。
また、移動可能マスは連結している。

これらの移動可能マスのうち、残りの移動可能マスを連結に保ちながら、K個を移動不可能マスにせよ。

解法

自分の行った解法では、適当な移動可能マスからスタートしてDFSし、奥から順にK個埋めていった。
ただ、もっと簡単な解法として、まず全部埋めてから、適当な移動可能マスからDFSで(移動可能マス数)-K個移動可能マスに戻す方が楽っぽい。

int H,W,K;
string S[501];
vector<pair<int,int> > PP;
int vis[501][501];

int dfs(int x,int y,int prex,int prey) {
	int dx[4]={1,-1,0,0};
	int dy[4]={0,0,1,-1};
	int i;
	vis[y][x]=1;
	FOR(i,4) {
		int tarx=x+dx[i];
		int tary=y+dy[i];
		if(tarx<0 || tarx>=W || tary<0 || tary>=H) continue;
		if(tarx==prex && tary==prey) continue;
		if(vis[tary][tarx]) continue;
		if(S[tary][tarx]=='#') continue;
		dfs(tarx,tary,x,y);
	}
	PP.push_back(make_pair(x,y));
}

void solve() {
	int f,i,j,k,l,x,y;
	int sx,sy;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='.') sx=x,sy=y;
	}
	
	dfs(sx,sy,-1,-1);
	FOR(i,K) S[PP[i].second][PP[i].first]='X';
	FOR(y,H) cout << S[y] << endl;
	
}

まとめ

Aの割にはややこしい問題で、結構落とす人がいたようだ。