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<iostream>
#include<sstream>
#include<vector>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fr(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

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;
	
}