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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct UnionFind {
  int parent[1010 * 1010];
  UnionFind() { memset(parent, -1, sizeof(parent)); }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) { return false; }
    if (parent[y] < parent[x]) { swap(x, y); }
    parent[x] += parent[y];
    parent[y] = x;
    return true;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
};

int n;
int w, h;
char field[1010][1010];
int gx, gy;
int xs[1010];
int ys[1010];
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
UnionFind ufind;

void Merge(int x, int y) {
  if (field[y][x] == '#') { return; }
  REP(dir, 4) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (nx < 0 || nx >= w || ny < 0 || ny >= h || field[ny][nx] == '#') { continue; }
    ufind.unionSet(y * w + x, ny * w + nx);
  }
}

int main() {
  while (scanf("%d %d", &w, &h) > 0) {
    ufind = UnionFind();
    REP(y, h) {
      scanf("%s", field[y]);
      REP(x, w) {
        if (field[y][x] == 't') { gx = x; gy = y; }
      }
    }
    scanf("%d", &n);
    REP(i, n) { scanf("%d %d", &xs[i], &ys[i]); }
    int ans = -1;
    REP(y, h) REP(x, w) {
      Merge(x, y);
    }
    if (ufind.findSet(0, gy * w + gx)) {
      ans = 0;
    } else {
      REP(i, n) {
        field[ys[i]][xs[i]] = '.';
        Merge(xs[i], ys[i]);
        if (ufind.findSet(0, gy * w + gx)) {
          ans = i + 1;
          break;
        }
      }
    }
    printf("%d\n", ans);
  }
}