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<algorithm>
#define INF 100000000
using namespace std;
int m[1000001],W,H;

int find(int x){
  if(m[x]==x) return m[x];
   return m[x]=find(m[x]);
}

void unite(int b,int a){
  int x=find(b);
  int y=find(a);
  if(x<y) swap(x,y);
  m[x]=y;
}

int cha(int x,int y){
  return y*W+x;
}

int main(){
  int dx[4]={-1,0,1,0};
  int dy[4]={0,-1,0,1};
  int N,wp,now,aft;
  string str;

  cin>>W>>H;
  for(int i=0;i<H;i++){
    cin>>str;
    for(int j=0;j<W;j++){
      int p=cha(j,i);
      if(str[j]=='t') wp=p;
      if(str[j]=='#') m[p]=INF;
      else  m[p]=p;
    }
  }
  
  int ax,ay,ans=-1;
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      for(int k=0;k<4;k++){
      now=cha(j,i);
      ax=j+dx[k],ay=i+dy[k];
      if(ax<0 || ay<0 || ax>=W || ay>=H || m[now]==INF) continue;
      aft=cha(ax,ay);
      if(m[aft]<INF ) unite(now,aft);
      }
    }
  }
  if(find(m[wp])==0) ans=0; 
  
   cin>>N;
  
   int x,y;

  for(int i=1;i<=N;i++){
    cin>>x>>y;
    int a=cha(x,y);
    if(m[a]==INF) m[a]=a;
    for(int j=0;j<4;j++){
      ax=x+dx[j],ay=y+dy[j];
      if(ax<0 || ay<0 || ax>=W || ay>=H ||m[cha(ax,ay)] == INF) continue;
   aft=cha(ax,ay);
      unite(a,aft);
      }
    if(find(m[wp])==0 && ans==-1) ans=i;
  }
   cout<<ans<<endl;
  return 0;
}