Problem: Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

10 10
.....#....
.....#....
.....#....
######....
..........
####......
....###...
t..#..####
...##.....
....#...##
3
0 3
0 5
4 6


Output

2

Solution (in CPP):

Solution:
#include<cstdio>
#include<vector>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int dx[]={0,-1,0,1},dy[]={-1,0,1,0};

class union_find{
	vector<int> a;
public:
	union_find(int n):a(n,-1){}
	int find(int x){
		if(a[x]<0) return x;
		return a[x]=find(a[x]);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x!=y){ a[x]+=a[y]; a[y]=x; }
	}
};

int main(){
	int w,h; scanf("%d%d",&w,&h);
	static char B[1000][1001];
	int gx,gy;
	rep(i,h){
		scanf("%s",B[i]);
		rep(j,w) if(B[i][j]=='t') gx=j, gy=i;
	}

	union_find U(h*w);
	rep(i,h) rep(j,w) if(B[i][j]!='#') {
		rep(k,2){
			int y=i+dy[k],x=j+dx[k];
			if(0<=y && y<h && 0<=x && x<w && B[y][x]!='#') U.unite(i*w+j,y*w+x);
		}
	}
	if(U.find(0)==U.find(gy*w+gx)){ puts("0"); return 0; }

	int n; scanf("%d",&n);
	rep(t,n){
		int i,j; scanf("%d%d",&j,&i);
		B[i][j]='.';
		rep(k,4){
			int y=i+dy[k],x=j+dx[k];
			if(0<=y && y<h && 0<=x && x<w && B[y][x]!='#') U.unite(i*w+j,y*w+x);
		}
		if(U.find(0)==U.find(gy*w+gx)){ printf("%d\n",t+1); return 0; }
	}

	puts("-1");

	return 0;
}