立命館合宿2012 day3 問題C Lucky Dip (AOJ 2364)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2364）

制約条件

w,h≦1000
n≦1000

方針

マスとマスがつながっているかを、Union-Findで持っておく。
新たなマスが'.'に変わるたびに、隣接する'.'のマスとmergeする。
これを繰り返して、スタートとゴールが同じunionに入った時点で秒数を出力する。

二分探索+BFSでもいい。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int p[1000*1000];
int root(int x){
	return x==p[x]?x:p[x]=root(p[x]);
}
void merge(int a,int b){
	a=root(a); b=root(b);
	if(a!=b)p[a]=b;
}
int h,w,g;
string in[1000];
int main(){
	cin>>w>>h;
	rep(i,h)cin>>in[i];
	rep(i,h*w){
		p[i]=i;
		if(in[i/w][i%w]=='t')g=i;
	}
	rep(i,h)rep(j,w)if(in[i][j]!='#'){
		rep(d,4){
			int y=i+dy[d],x=j+dx[d];
			if(0<=y&&y<h&&0<=x&&x<w&&in[y][x]!='#')
			merge(y*w+x,i*w+j);
		}
	}
	int n; cin>>n;
	if(root(g)==root(0)){
		cout<<0<<endl; return 0;
	}
	rep(i,n){
		int tx,ty; cin>>tx>>ty;
		in[ty][tx]='.';
		rep(d,4){
			int y=ty+dy[d],x=tx+dx[d];
			if(0<=y&&y<h&&0<=x&&x<w&&in[y][x]!='#')
			merge(y*w+x,ty*w+tx);
		}
		if(root(g)==root(0)){
			cout<<i+1<<endl; return 0;
		}
	}
	cout<<-1<<endl;
		
	return 0;
	
}