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>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

struct UnionFind {
  vector<int> parent;
  UnionFind (int n) : parent(n, -1) {}
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (parent[y] < parent[x]) swap(x, y);
    if (parent[x] == parent[y]) --parent[x];
    parent[y] = x;
    return true;
  }
};

int main() {
  int w,h;
  cin>>w>>h;
  vector<string> t(h);
  REP(i,h) cin>>t[i];
  UnionFind uf(w*h);
  REP(i,h)REP(j,w-1) {
    if (t[i][j] != '#' && t[i][j+1] != '#')
      uf.merge(i*w+j, i*w+j+1);
  }
  REP(i,h-1)REP(j,w) {
    if (t[i][j] != '#' && t[i+1][j] != '#')
      uf.merge(i*w+j, (i+1)*w+j);
  }
  int ti=0,tj=0;
  REP(i,h)REP(j,w) {
    if(t[i][j] == 't') {
      ti=i;tj=j;
    }
  }
  int n;
  cin>>n;
  bool ok = false;
  REP(i,n) {
    if (uf.root(0) == uf.root(ti*w+tj)) {
      cout << i << endl;
      ok = true;
      break;
    }
    int x,y;
    cin>>x>>y;
    t[y][x] = '.';
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};
    REP(j,4) {
      int nx=x+dx[j], ny=y+dy[j];
      if(nx<0||nx>=w||ny<0||ny>=h)continue;
      if(t[ny][nx] != '#')
        uf.merge(y*w+x, ny*w+nx);
    }
  }
  if (!ok) {
    if (uf.root(0) == uf.root(ti*w+tj)) {
      cout << n << endl;
    } else {
      cout << -1 << endl;
    }
  }
  return 0;
}