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 UnionFind{
  vector<int> par, rank;
public:
  UnionFind(int n=1){
    par.resize(n);
    for(int i=0;i<n;i++)par[i] = i;
    rank = vector<int>(n,0);
  }

  int find(int x){ return par[x] = par[x]==x?x:find(par[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(rank[x] < rank[y])par[x] = y;
    else{
      par[y] = x;
      if(rank[x] == rank[y])rank[x]++;
    }
  }
};

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

int main(){
  int w,h,n,x,y,goal = -1;
  string g[1010];

  cin >> w >> h;

  UnionFind uf(h*w);
  for(int i=0;i<h;i++){
    cin >> g[i];
    for(int j=0;j<w;j++){
      if(g[i][j] == 't')goal = i*w + j;
      if(g[i][j] != '#'){
	for(int d=0;d<4;d++){
	  int ny = i+dy[d], nx = j+dx[d];
	  if(ny<0 || nx<0 || ny>=h || nx>=w)continue;
	  if(g[ny][nx] !='#')uf.unite(i*w+j,ny*w+nx);
	}
      }
    }
  }

  cin >> n;
  int ans = -1;
  for(int i=0;i<=n;i++){
    if(i){
      cin >> x >> y;
      g[y][x] = '.';
      for(int d=0;d<4;d++){
	int ny = y+dy[d], nx = x+dx[d];
	if(ny<0 || nx<0 || ny>=h || nx>=w)continue;
	if(g[ny][nx] !='#')uf.unite(y*w+x,ny*w+nx);
      }
    }

    if(ans<0 && uf.same(0,goal))ans = i;
  }
  cout << ans << endl;
}