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<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e8;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
typedef struct{
	int x,y;
} q;
int n,m,a;
int main(){
	cin>>m>>n;
	vector<vector<char> >in(n+2,vector<char>(m+2));
	rep(i,n+2)rep(j,m+2){
		if(!i||!j||i==n+1||j==m+1)in[i][j]='#';
		else cin>>in[i][j];
	}
	cin>>a;
	vector<q>s(a+1);
	rep(i,a){
		cin>>s[i+1].y>>s[i+1].x;
		s[i+1].x++;s[i+1].y++;
	}
	bool h=false;
	rep(i,a+1){
		vector<q>tmp;
		if(!i){q qq={1,1};tmp.pb(qq);in[1][1]='!';}
		else{
			bool h1=false;
			rep(j,4)if(in[s[i].x+dx[j]][s[i].y+dy[j]]=='!')h1=true;
			if(h1){tmp.pb(s[i]);in[s[i].x][s[i].y]='!';}
			else in[s[i].x][s[i].y]='.';
		}
		while(tmp.size()){
			//cout<<tmp[0].x<<" "<<tmp[0].y<<endl;
			rep(j,4){
				int nx=tmp[0].x+dx[j];
				int ny=tmp[0].y+dy[j];
				if(in[nx][ny]=='t'){h=true;break;}
				if(in[nx][ny]=='.'){
					q qq={nx,ny};
					tmp.pb(qq);
					in[nx][ny]='!';
				}
			}
			tmp.erase(tmp.begin());
			if(h){cout<<i<<endl;return 0;}
		}
	/*rep(j,n+2){
			rep(k,m+2)cout<<in[j][k];
			cout<<endl;
		}
		cout<<endl;*/
	}
	cout<<-1<<endl;
}