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 <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit
#include <cstdio>	// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>	// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define DEBUG 0

using namespace std;

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(){
//	freopen ("testcase.lucky_dip", "r", stdin );

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