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;

#define int long long
#define MAX 1100
int _rank[MAX*MAX], per[MAX*MAX];

void init(){
  for(int i = 0; i < MAX*MAX; i++){
    _rank[i] = 1;
    per[i] = i;
  }
}

int find(int x){
  return x == per[x]? x : per[x] = find(per[x]);
}

void unite(int x, int y){
  y = find(y);
  x = find(x);

  if(x == y) return;

  if(_rank[y] > _rank[x]){
    per[x] = y;
  } else {
    per[y] = x;
    if(_rank[y] == _rank[x]) _rank[x]++;
  }
}

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


signed main(){
  int W, H, N;
  int tx, ty;
  int x, y;
  static string T[MAX];

  int dxy[4] = {0,0,1,-1};

  cin>>W>>H;

  for(int i = 0; i < H; i++){
    cin>>T[i];
  }

  init();
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){

      if(T[i][j] == 't'){
	ty = i;
	tx = j;
      }
	if(T[i][j] == '#') continue;
	
      for(int k = 0; k < 4; k++){
	int nx = j + dxy[k], ny = i + dxy[3 - k];

	if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

	if(T[ny][nx] == '#') continue;

	unite(i*MAX + j, ny*MAX + nx);
      }
    }
  }
  cin>>N;

  if(same(0,ty*MAX + tx)){
    cout<<0<<endl;
    return 0;
  }

  for(int i = 0; i < N; i++){
    cin>>x>>y;
    
    if(T[y][x] == '.') continue;
    T[y][x] = '.';
    
    for(int k = 0; k < 4; k++){
      int nx = x + dxy[k], ny = y + dxy[3 - k];
      
      if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
      
      if(T[ny][nx] == '#') continue;

      unite(y*MAX + x, ny*MAX + nx);
    }


    if(same(0, ty*MAX + tx)){
      cout<<i+1<<endl;
      return 0;
    }
  }


  cout<<-1<<endl;
  return 0;
}