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<stdio.h>
#include<iostream>
using namespace std;

//union_find begin
#define MAX 5000000
struct node{  int parent,size; };
node tree[MAX];
void init(){
  for(int i=0;i<MAX;i++){
    tree[i].parent=i;
    tree[i].size=1;    
  }
}
/*
int find(int x){ 
  if(tree[x].parent==x)return x;
  tree[x].parent = find( tree[x].parent );
  return tree[x].parent;
}
*/
int st[MAX],cnt;
int find(int x){
  cnt=0;
  while(tree[x].parent!=x){    
    st[cnt++]=x;
    x=tree[x].parent;
  }
  while(cnt>0){
    cnt--;
    tree[st[cnt]].parent=x;
  }
  return x;
}

int count(int x){
  x=find(x);
  return tree[x].size;
}

bool same(int x,int y){
  return ( find(x) == find(y) );
}

void unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y)return;  
  if(count(x)>count(y))swap(x,y);
  tree[x].parent=y;
  tree[y].size+=tree[x].size;
}
// union find end

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int W,H,N,target;
char t[1005][1005];

int change(int i,int j){
  return i*W+j;
}

int solve(){
  if(same(0,target))return 0;
  scanf("%d",&N);
  for(int ans=1;ans<=N;ans++){
    int i,j;
    scanf("%d %d",&j,&i);
    if(t[i][j]=='.')continue;
    t[i][j]='.';
    for(int k=0;k<4;k++){
      int ni=i+dy[k];
      int nj=j+dx[k];
      if(ni<0 || nj<0 || H<=ni || W<=nj)continue;
      if(t[ni][nj]=='#')continue;
      unite( change(i,j) , change(ni,nj) );
    }
    if(same(target,0))return ans;
  }
  return -1;
}

int main(){
  init();
  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]=='t')target=change(i,j);
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(t[i][j]=='#')continue;
      for(int k=0;k<4;k++){
        int ni=i+dy[k];
        int nj=j+dx[k];
        if(ni<0 || nj<0 || H<=ni || W<=nj)continue;
        if(t[ni][nj]=='#')continue;
        unite( change(i,j) , change(ni,nj) );
      }
    }
  }
  printf("%d\n",solve());
  return 0;
}