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<stdio.h>
#include<algorithm>
using namespace std;
int UF[1100000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char str[1100][1100];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a*b;i++)UF[i]=-1;
	for(int i=0;i<b;i++){
		scanf("%s",str[i]);
	}
	int gx,gy;
	for(int i=0;i<b;i++)for(int j=0;j<a;j++){
		if(str[i][j]=='#')continue;
		if(str[i][j]=='t'){gx=i;gy=j;}
		for(int k=0;k<4;k++){
			if(0<=i+dx[k]&&i+dx[k]<b&&0<=j+dy[k]&&j+dy[k]<a&&str[i+dx[k]][j+dy[k]]!='#')
				UNION((i+dx[k])*a+j+dy[k],i*a+j);
		}
	}
	if(FIND(0)==FIND(gx*a+gy)){printf("0\n");return 0;}
	int c;scanf("%d",&c);
	for(int i=0;i<c;i++){
		int p,q;scanf("%d%d",&q,&p);
		str[p][q]='.';
		for(int j=0;j<4;j++){
			if(0<=p+dx[j]&&p+dx[j]<b&&0<=q+dy[j]&&q+dy[j]<a&&str[p+dx[j]][q+dy[j]]!='#')
				UNION((p+dx[j])*a+q+dy[j],p*a+q);
		}
		if(FIND(0)==FIND(gx*a+gy)){
			printf("%d\n",i+1);
			return 0;
		}
	}
	printf("-1\n");
}