kmjp's blog

競技プログラミング参加記です

Codeforces ECR #001 : D. Igor In the Museum

こっちは妙なひっかけもなく素直な問題。
http://codeforces.com/contest/598/problem/D

問題

N*Mマスのグリッド状に区切られた美術館がある。
一部のマスは壁となっていて進入不可であり、その壁の外周には(隣も壁になっていない限り)絵が貼ってあり隣のセルから閲覧可能である。

ここで美術館のグリッドの状態と、K個のクエリが与えられる。
各クエリではマスの位置が指定されるので、隣接セルを辿って閲覧可能な絵の数を求めよ。

解法

未訪問の移動可能セルが来たら、そこからDFSで移動可能なセルを列挙しよう。
その過程で、各セルから移動不可能な隣接セル数は閲覧可能な絵の数に一致するので、そのようなセル数を数え上げていけば良い。

int H,W,K;
string S[1010];

int num[1010][1010];
int base[1010][1010];

void dfs(int cy,int cx,int by,int bx) {
	base[cy][cx]=by*10000+bx;
	int i;
	FOR(i,4) {
		int dd[4]={1,0,-1,0};
		int ty=cy+dd[i];
		int tx=cx+dd[i^1];
		if(S[ty][tx]=='.') {
			if(base[ty][tx]==-1) dfs(ty,tx,by,bx);
		}
		else num[by][bx]++;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) cin>>S[y];
	MINUS(base);
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='.' && base[y][x]==-1) dfs(y,x,y,x);
	
	FOR(i,K) {
		cin>>j>>k;
		y = base[j-1][k-1]/10000;
		x = base[j-1][k-1]%10000;
		cout<<num[y][x]<<endl;
	}
	
}

まとめ

いまいちECRの狙いがわからないな…。