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 <string>
#define N1 (1000+1)
using namespace std;
int find(int);
void unite(int,int);
bool same(int,int);
int tree[N1*N1];
string str[N1];
int main(){
  int W,H,N,x,y,findy,findx;
  int dx[4]={0,1,0,-1};
  int dy[4]={-1,0,1,0};
  cin >> W >> H;
  for(int i=0;i<H;i++) cin >> str[i];
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      tree[i*W+j]=i*W+j;      
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(str[i][j]=='t') findy=i,findx=j;
      if(str[i][j]!='#'){
	for(int k=0;k<4;k++)
	  if(0<=i+dy[k]&&i+dy[k]<H&&0<=j+dx[k]&&j+dx[k]<W)
	    if(str[i+dy[k]][j+dx[k]]!='#')
	      unite(i*W+j,(i+dy[k])*W+(j+dx[k]));
      }
    }
  }
  cin >> N;
  int flag=0;
  if(same(0,findy*W+findx)){
    flag=1;
    cout << 0 << endl;
  }
  int cnt=0;
  while(N--&&flag==0){
    cnt++;
    cin >> x >> y;
    str[y][x]='.';
    for(int i=0;i<4;i++)
      if(0<=y+dy[i]&&y+dy[i]<H&&0<=x+dx[i]&&x+dx[i]<W&&str[y+dy[i]][x+dx[i]]!='#')
	unite(y*W+x,(y+dy[i])*W+(x+dx[i]));
    if(same(0,findy*W+findx)){
      flag=1;
      cout << cnt << endl;
      break;
    }
  }
  if(flag==0) cout << -1 << endl;
  return 0;
}
int st[N1*N1];
int find(int x){
  int cnt=0;
  while(x!=tree[x]){
    x=tree[x];
    st[cnt]=x;
    cnt++;
  }
  while(cnt>0){
    cnt--;
    tree[st[cnt]]=x;
  }
  return x;
}
void unite(int x,int y){
  x=find(x),y=find(y);
  if(x==y) return ;
  if(x<y) swap(x,y);
  tree[x]=y;
}
bool same(int x,int y){
  if(find(x)==find(y)) return true;
  return false;
}