kmjp's blog

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

Codeforces #301 Div2 C. Ice Cave

Codeforces

CF#301は不参加なので練習。
B,Cが妙にコーナーケースが多くてはまった。
http://codeforces.com/contest/540/problem/C

問題

２次元グリッドが与えられる。
各セルは壊れやすい氷か頑丈な氷である。

壊れやすい氷のセルは、乗ると即座に壊れて下の階に落とされる。
頑丈な氷のセルは、一旦乗ることができるがその時点で壊れやすい氷のセルになり、再度乗ると下の階に落とされる。

グリッド上で始点と終点の２つセル位置が指定される。
始点セルから初めて隣接セルを辿って移動していく場合、終点セルで下の階に落ちることは可能か。

解法

終点セルが壊れやすいなら、そこに到達可能なら問題文の条件を満たす。
終点セルが頑丈なら、そこに到達する経路以外で、終点セルの隣接１つ頑丈なセルがあればよい。

実際は場合分けが気味にめんどくさい。

  • 始点==終点の場合：
    • 終点セルが頑丈なら、隣接セルに頑丈なセルが２個以上あればよい。
    • 終点セルが壊れやすいなら、隣接セルに頑丈なセルが１個以上あればよい。
  • 始点と終点の距離が１の場合：
    • 終点セルが頑丈なら、隣接セルに頑丈なセルが１個以上あればよい。
    • 終点セルが壊れやすいなら、条件を満たせる。
  • 始点と終点の距離が２以上の場合：
    • まず前提として、始点の頑丈な隣接セルから、頑丈なセルだけたどって終端の隣接セルに行けること。
      • これはBFSなりUnion-Findで検索可能。
    • その上で、終点セルが頑丈なら、隣接セルに頑丈なセルが２個以上あればよい。
template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

int H,W;
string S[1010];
int X[2],Y[2];

int getadjok(int y,int x) {
	int num=0;
	if(y>0 && S[y-1][x]=='.') num++;
	if(y<H-1 && S[y+1][x]=='.') num++;
	if(x>0 && S[y][x-1]=='.') num++;
	if(x<W-1 && S[y][x+1]=='.') num++;
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>H>>W;
	
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) if(S[y][x]=='.') {
		if(x<W-1 && S[y][x+1]=='.') uf(y*500+x,y*500+x+1);
		if(y<H-1 && S[y+1][x]=='.') uf(y*500+x,(y+1)*500+x);
	}
	FOR(i,2) cin>>Y[i]>>X[i], Y[i]--,X[i]--;
	
	if(abs(X[1]-X[0])+abs(Y[1]-Y[0])<=1) {
		int adj=abs(X[1]-X[0])+abs(Y[1]-Y[0]);
		if(S[Y[1]][X[1]]=='.' && getadjok(Y[1],X[1])+adj>=2) return _P("YES\n");
		if(S[Y[1]][X[1]]=='X' && getadjok(Y[1],X[1])+adj>=1 && H*W>1) return _P("YES\n");
	}
	else if(S[Y[1]][X[1]]=='.') {
		int ok=0;
		FOR(i,4) {
			int dd[]={-1,0,1,0};
			int ty=Y[0]+dd[i],tx=X[0]+dd[i^1];
			if(tx>=0 && tx<W && ty>=0 && ty<H && uf[ty*500+tx]==uf[Y[1]*500+X[1]] && S[ty][tx]!='X') ok=1;
		}
		if(ok && getadjok(Y[1],X[1])>=2) return _P("YES\n");
	}
	else {
		FOR(i,16) {
			int dd[]={-1,0,1,0};
			int ty=Y[0]+dd[i%4],tx=X[0]+dd[(i%4)^1];
			int sy=Y[1]+dd[i/4],sx=X[1]+dd[(i/4)^1];
			if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
			if(sx<0 || sx>=W || sy<0 || sy>=H) continue;
			if(uf[ty*500+tx]==uf[sy*500+sx] && S[ty][tx]!='X' && S[sy][sx]!='X') return _P("YES\n");
		}
	}
	_P("NO\n");
	
}

まとめ

Editorial見ても細かく場合分けしてるけど、DFSでさらっと短く書いてる人もいるね。