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;

class uf{
  int n;
  vector<int> rank, parent;
public:
  uf();
  uf(int _n){
    init(_n);
  }
  void init(int _n){
    n = _n;
    rank.resize(n);
    parent.resize(n);
    for (int i = 0; i < n; i++) {
      rank[i] = 0;
      parent[i] = i;
    }
  }
  int find(int x){
    if(x == parent[x])return x;
    else return parent[x] = find(parent[x]);
  }
  
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      parent[x] = y;
    }else{
      parent[y] = x;
      if(rank[x] == rank[y])rank[x]++;
    }
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
  void printParent(){
    for (int i = 0; i < n; i++) {
      std::cout << parent[i] << " ";
    }
    std::cout << std::endl;
  }
};
int dx[] = {1, 0, -1, 0},
  dy[] = {0, 1, 0, -1};

int main(int argc, char *argv[]){
  int w, h, n, ans = 0;
  std::cin >> w >> h;
  vector<string> grid(h);
  for (int i = 0; i < h; i++) {
    std::cin >> grid[i];
    for (int j = 0; j < w; j++) {
      if(grid[i][j] == 't')ans = i*w + j;
    }
  }
  uf u(w*h);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if(grid[i][j] != '.')continue;
      for (int k = 0; k < 4; k++) {
        int nx = j + dx[k], ny = i + dy[k];
        if(!(0 <= nx && nx < w &&
             0 <= ny && ny < h))continue;
        if(grid[ny][nx] == '#')continue;
        u.unite(i*w + j, ny*w + nx);
      }
    }
  }
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    int x, y;
    std::cin >> x >> y;
    if(u.find(0) == u.find(ans)){
      std::cout << i << std::endl;
      return 0;
    }
    grid[y][x] = '.';
    for (int j = 0; j < 4; j++) {
      int nx = x + dx[j], ny = y + dy[j];
      if(!(0 <= nx && nx < w &&
           0 <= ny && ny < h))continue;
      if(grid[ny][nx] == '#')continue;
      u.unite(y*w + x, ny*w + nx);
    }

  }
  if(u.find(0) == u.find(ans)){
    std::cout << n << std::endl;
  }else{
    std::cout <<  -1 << std::endl;
  }
  return 0;
}