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>
#include <vector>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
const int INF = (int)1e9;
struct UnionFind {
  vector<int> data;
  UnionFind(int v) : data(v, -1) { }
  int root(int x) {
    return data[x] < 0 ? x : (data[x] = root(data[x]));
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
  void merge(int x, int y) {
    x = root(x), y = root(y);
    if(x != y) {
      if(size(y) > size(x)) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
  }
};
char M[1000][1001];
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
int main() {
  ios::sync_with_stdio(false);
  int W, H; cin >> W >> H;
  REP(i,H) cin >> M[i];
  int N; cin >> N;
  UnionFind U(1000*1000);
  int ty, tx;
  REP(i,H) REP(j,W) REP(k,4) {
    if(M[i][j] == 't') {
      ty = i;
      tx = j;
      M[ty][tx] = '.';
    }
    int ny = i + dy[k];
    int nx = j + dx[k];
    if(ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
    if(M[i][j] == '.' && M[ny][nx] == '.') {
      // cerr << "merge " << i << ", " << j << " <=> " << ny << ", " << nx << endl;
      U.merge(i*1000+j, ny*1000+nx);
    }
  }
  int ans = INF;
  if(U.same(0, ty*1000+tx)) ans = 0;
  REP(n, N) {
    int j, i; cin >> j >> i;
    M[i][j] = '.';
    REP(k,4) {
      int ny = i + dy[k];
      int nx = j + dx[k];
      if(ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
      if(M[i][j] == '.' && M[ny][nx] == '.') {
        // cerr << "merge " << i << ", " << j << " <=> " << ny << ", " << nx << endl;
        U.merge(i*1000+j, ny*1000+nx);
      }
    }
    if(U.same(0, ty*1000+tx)) {
      ans = min(ans, n + 1);
    }
  }
  if(ans == INF) cout << -1 << endl;
  else cout << ans << endl;
}