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 <algorithm>
#include <queue>

using namespace std;

const int INFTY=1<<29;

int grid[1000][1000],vis[1000][1000];
int xs[1000],ys[1000];
int w,h;
int di[]={-1,1,0,0},dj[]={0,0,-1,1};

bool ok(int time)
{
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			vis[i][j]=0;
	
	queue<pair<int,int> > q;
	q.push(make_pair(0,0));
	while(q.size()){
		int i=q.front().first,j=q.front().second;
		q.pop();
		if(vis[i][j])
			continue;
		vis[i][j]=1;
		if(grid[i][j]==-1)
			return true;
		
		for(int k=0;k<4;k++){
			int ni=i+di[k],nj=j+dj[k];
			if(0<=ni && ni<h && 0<=nj && nj<w && grid[ni][nj]<=time)
				q.push(make_pair(ni,nj));
		}
	}
	return false;
}

int main()
{
	while(~scanf("%d%d ",&w,&h) && w|h){
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				int c=getchar();
				if(c=='t') grid[i][j]=-1;
				if(c=='#') grid[i][j]=INFTY;
				if(c=='.') grid[i][j]=0;
			}
			getchar();
		}
		int n; scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%d%d",xs+i,ys+i);
		
		for(int i=0;i<n;i++)
			grid[ys[i]][xs[i]]=min(grid[ys[i]][xs[i]],i+1);
		for(int i=0;i<h;i++)
			for(int j=0;j<w;j++)
				grid[i][j]=min(grid[i][j],n+1);
		
		int lo=-1,hi=n+1;
		while(hi-lo>1){
			int mi=(lo+hi)/2;
			if(ok(mi))
				hi=mi;
			else
				lo=mi;
		}
		printf("%d\n",hi==n+1?-1:hi);
	}
	return 0;
}