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<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int W,H,N;
char t[1000][1001];
int change(int i,int j){return i*W+j;}
int a[1000][1000];
int d[1000000];

int solve(){
  memset(d,1,sizeof(d));

  priority_queue< P , vector<P> , greater<P> > Q;
  Q.push(P(0,0));
  d[0]=0;
  while(!Q.empty()){
    P p=Q.top();Q.pop();
    int i=p.second/W;
    int j=p.second%W;
    int cost=p.first;
    //cout<<i<<' '<<j<<' '<<cost<<endl;
    if(cost > d[p.second])continue;
    if(t[i][j]=='t')return cost;
    for(int k=0;k<4;k++){
      int ni=i+dy[k];
      int nj=j+dx[k];
      int to=ni*W+nj;
      if(ni<0||nj<0)continue;
      if(H<=ni||W<=nj)continue;
      int ncost=max(cost,a[ni][nj]);
      if(ncost < d[to]){
        d[to]=ncost;
        Q.push(P(d[to],to));
      }
    }
  }
  return -1;
}

int main(){
  scanf("%d %d",&W,&H);
  for(int i=0;i<H;i++){
    scanf("%s",t[i]);
    for(int j=0;j<W;j++){
      if(t[i][j]=='#')a[i][j]=1e8;
    }
  }
  scanf("%d",&N);
  for(int A=1;A<=N;A++){
    int i,j;
    scanf("%d %d",&j,&i);
    if(t[i][j]=='#'){
      a[i][j]=A;
      t[i][j]='.';
    }
  }
  printf("%d\n",solve());
  return 0;
}