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:
//Disjoint Set
//Accepted
//uva 793,273,10685
//
#include<iostream>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n) 

class DisjointSet{
public:
 vector<int> rank,p;
 DisjointSet(){}
 DisjointSet(int size){
   rank.resize(size,0);
   p.resize(size,0);
 }
 void make_set(int x){
   p[x]=x;
   rank[x]=0;
 }
 void merge(int x,int y){
   link(find_set(x),find_set(y));
 }
 void link(int x,int y){
   if (rank[x]>rank[y]){
     p[y]=x;
   }else {
     p[x]=y;
     if ( rank[x] ==rank[y])rank[y]+=1;
   }
 }
 int find_set(int x){
   if (x != p[x])p[x]=find_set(p[x]);
   return p[x];
 }
};

const int N = 1000;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
char m[N][N+10];

void update(int r,int c,int i,int j,DisjointSet & dj){
  if (m[i][j] == '#')return;
  rep(k,4){
    int nex = j+dx[k],ney = i+dy[k];
    if (ney == -1 || nex == -1 || ney == r || nex == c || m[ney][nex] == '#')continue;
    dj.merge(ney*c+nex,i*c+j);
  }
}

DisjointSet dj(1000*1000);
int solve(int r,int c,vector<int> & t,int gy,int gx){
  rep(i,r*c)dj.make_set(i);
  rep(i,r)rep(j,c)update(r,c,i,j,dj);
  if (dj.find_set(0) == dj.find_set(gy*c+gx))return 0;
  rep(i,t.size()){
    m[t[i]/c][t[i]%c] = '.';
    update(r,c,t[i]/c,t[i]%c,dj);
    if (dj.find_set(0) == dj.find_set(gy*c+gx))return i+1;
  }
  return -1;
}

int main(){
  int r,c;
  while(cin>>c>>r && r){
    rep(i,r){
      cin>>m[i];
    }
    int gy,gx;
    rep(i,r)rep(j,c)if (m[i][j] == 't')gy = i,gx = j;
    int t;cin>>t;
    vector<int> ti(t);
    rep(i,t){
      int y,x;
      cin>>x>>y;
      ti[i] = y*c+x;
    }
    cout << solve(r,c,ti,gy,gx) << endl;
  }
  return 0;
}