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

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

struct UnionFind{
  int n;
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  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(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
  int size(int x){
    return r[find(x)];
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int W, H;
  cin >> W >> H;  

  vector<string> s(H);
  for ( int i = 0; i < H; i++ ) {
    cin >> s[i];    
  }
  
  UnionFind uf((W+1)*(H+1));

  int g;
  for ( int i = 0; i < H; i++ ) {
    for ( int j = 0; j < W; j++ ) {
      // cout << i << " " << j << endl;
      if ( s[i][j] == '.' ) {
	for ( int k = 0; k < 4; k++ ) {
	  int ny = i+dy[k], nx = j+dx[k];
	  if ( ny < 0 || ny >= H || nx < 0 || nx >= W ) continue;	  
	  if ( s[ny][nx] == '.' || s[ny][nx] == 't' ) uf.unite(i*W+j, ny*W+nx);	  
	}
      }
      if ( s[i][j] == 't' ) {
	g = i*W+j;	
	for ( int k = 0; k < 4; k++ ) {
	  int ny = i+dy[k], nx = j+dx[k];
	  if ( ny < 0 || ny >= H || nx < 0 || nx >= W ) continue;	  
	  if ( s[ny][nx] == '.' || s[ny][nx] == 't' ) uf.unite(i*W+j, ny*W+nx);	  
	}
      }
    }
  }

  int N;
  cin >> N;
 
  int ans = -1;

  if ( uf.same(0, g) ) ans = 0;  
  
  for ( int i = 0; i < N; i++ ) {
    int x, y;
    cin >> x >> y;
    s[y][x] = '.';    
    if ( ans >= 0 ) continue;
    for ( int k = 0; k < 4; k++ ) {
      int ny = y+dy[k], nx = x+dx[k];
      if ( ny < 0 || ny >= H || nx < 0 || nx >= W ) continue;	  
      if ( s[ny][nx] == '.' || s[ny][nx] == 't' ) uf.unite(y*W+x, ny*W+nx);      
    }

    if ( uf.same(0, g) ) ans = i+1;    
  }

  cout << ans << endl;

  return 0;
}