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<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#define F first
#define S second

using namespace std;

static const int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
int par[1010*1010];

int find(int x){
  if(x == par[x])return x;
  return par[x]=find(par[x]);
}

void unit(int x,int y){
  x = find(x);
  y = find(y);
  if(x!=y){
    par[x] = y;
  }
}


int main(){
  int w,h,g;
  char cmap[1100][1100];
  cin >> w >> h;
  for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin >> cmap[i][j];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      par[j+i*w] = j+i*w;
      if(cmap[i][j] == 't')g = j+i*w;
    }
  }
 

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(cmap[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 && cmap[ny][nx] != '#'){
	    unit(nx+ny*w,j+i*w); 
	  }
      }
    }
  }




    bool Zero = false;
    if(find(g) == find(0))Zero = true;
 
 
    int n,cnt=-1;
    cin >> n;
    
    for(int i=0;i<n;i++){
      int inx,iny;
      cin >> inx >> iny;
      cmap[iny][inx] = '.';
      for(int k=0;k<4;k++){
	int nx = inx+dx[k],ny = iny+dy[k];
	if(0<=nx && nx < w && 0<= ny && ny < h && cmap[ny][nx] != '#'){
	  unit(nx+ny*w,inx+iny*w);
	}
      }
      if(find(0) == find(g) && cnt == -1){
	cnt = i+1;
      }

    }



    if(Zero){
      cout << 0 << endl;
    }
    else{
      cout << cnt << endl;
    }

  return 0;
}







////
/*

typedef pair<int,int> P;
static const int INF = (1<<29);
int h,w;
char cmap[1100][1100];
int par[1100][1100];
int rank[1100][1100];
P pos[1100];
bool used[1100][1100];
static const int dx[4] = {0,1,0,-1};
static const int dy[4] = {1,0,-1,0};


void init(){
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      par[i][j] = j+w*i;
      pos[j+w*i] = P(j,i);
      rank[i][j] = 0;
      used[i][j] = false;
    }
  }
}

int find(int x,int y){
  if(par[y][x] == (x+w*y))return (x+w*y);
  else return par[y][x] = find(pos[par[y][x]].F,pos[par[y][x]].S);
}

void unit(P x,P y){
  //cout <<"in unit, x(" << x.F << "," << x.S <<") " << ",y(" << y.F << "," <<y.S << ")" << endl;
  //int X = find(x.F,x.S);
  //cout << "X = " << X;
  //int Y = find(y.F,y.S);
  //cout << ",Y = " << Y << endl;
  //if(X == Y)return;
  int a = find(x.F,x.S),b = find(y.F,y.S);
  if(a != b){
    P p = pos[a];
    par[p.S][p.F] = b;
  }
  /*
  if(rank[x.S][x.F] < rank[y.S][y.F]){
    par[x.S][x.F] = y.F+y.S*h;
  }else{
    par[y.S][y.F] = x.F+x.S*h;
    if(rank[x.S][x.F] == rank[y.S][y.F])rank[x.S][x.F]++;
  }
  */


////////////////////
/*
}

*/
/////////////////////



//////////////////
/*
bool same(P x,P y){
  return find(x.F,x.S) == find(y.F,y.S);
}

void display()
{
  cout << "--------par---------" << endl;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cout << par[i][j] << " ";
    }
    cout << endl;
  }
  
  cout << "--------rank--------" << endl;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cout << rank[i][j] << " ";
    }
    cout << endl;
  }
}


void dfs(int x,int y){
  used[y][x] = true;
  //cout  <<"x = "<< x << ", y = " << y << endl;
  for(int i=0;i<4;i++){
    int nx = x+dx[i],ny = y+dy[i];
    //cout << "P(" << x << "," << y << ") nx = " << nx << " ny = "<< ny << endl;
    if(0<= nx && nx < w && 0<= ny && ny < h && !used[ny][nx] && cmap[ny][nx] != '#'){
      P A = P(x,y),B = P(nx,ny);
      unit(A,B);
      dfs(nx,ny);
    }
  }

}







int main(){
  cin >> w >> h;
    int gx,gy;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> cmap[i][j];
	if(cmap[i][j] == 't'){
	  gx = j;
	  gy = i;
	}
      }
    }
    //cout << "pre init" << endl;
    init();
    //cout << "pre dfs" << endl;
    
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(cmap[i][j] == '#')continue;
	if(!used[i][j])dfs(j,i);
	
      }
    }




 for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(cmap[i][j] == '#')continue;
	if(!used[i][j])dfs(j,i);
	
      }
    }
    
    /*
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(cmap[i][j] != '#'){
	  for(int k=0;k<4;k++){
	    int nx = j+dx[i],ny = i+dy[i];
	    if(0<=nx && nx <w && 0<=ny && ny<h && cmap[ny][nx] != '#'){
	      unit(P(nx,ny),P(j,i));
	    }
	  }
	}
      }
    }
    */
 //cout << "pre display" << endl;
 //display();


/////////////////////////
/*
 bool zero = false;
 int N;
 cin >> N;
 if(find(gx,gy) == find(0,0)){
   zero = true;
 }
 P p;
 int cnt = -1;
 for(int i=0;i<N;i++){
   cin >> p.F >> p.S;
   cmap[p.S][p.F] = '.';
   for(int j=0;j<4;j++){
     int nx = p.F+dx[j],ny = p.S+dy[j];
     if(0<= nx && nx < w && 0<= ny && ny < h && cmap[ny][nx] != '#'){
       unit(p,P(nx,ny));
     }
   }
   if(find(gx,gy) == find(0,0) && cnt == -1){
     //cout << i+1 << endl;
     //display();
     //cnt++;
     cnt = i+1;
   }
 }

 if(zero){
   cout <<0 << endl;
   return 0;
 }
 //display();
 
 if(cnt != -1)cout << cnt << endl;
 else cout << -1 << endl;






  
  return 0;
}







*/  ////