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<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<string>
#include<complex>
#define pb push_back
#define clr clear()
#define sz size()
#define EPS (1e-8)
#define INF 500000000
#define For(i,a) for(int i=0;i<(int)a;i++)
#define all (a) (a).begin(),(a).end()
#define RES(i) memset(i,0,sizeof(i))
#define EQ(a,b) (abs((a)-(b))<EPS)
#define let(i,a) __typeof(a)i=(a)
#define each(i,a) for(let(i,(a).begin());i!=(a).end();i++)

using namespace std;

typedef pair<int,int> P;
typedef long long ll;

string grid[1100];
bool vis[1100][1100];
int w,h,n;

int main(){
  int x,y;
  cin >> w >> h;

  For(i,h)cin >> grid[i];

  For(i,h)For(j,w)vis[i][j] = false;

  stack<P> q;
  q.push(P(0,0));
  set<P> s;

  while(q.size()){
    int y = q.top().first, x = q.top().second;
    q.pop();
    
    if(grid[y][x] == 't'){
      cout << 0 << endl;
      return 0;
    }
    
    vis[y][x] = true;
    int dy[] = {-1,0,1,0},dx[] = {0,1,0,-1};
    
    For(i,4){
      int sy = y + dy[i] , sx = x + dx[i];
      if(sy<0 || sx<0 || h<=sy || w<=sx)continue;
      if(vis[sy][sx])continue;
      if(grid[sy][sx] == '#'){
	s.insert(P(sy,sx));
	continue;
      }
      q.push(P(sy,sx));
    }
  }

  cin >> n;
  For(i,n){
    cin >> x >> y;
    if(grid[y][x]=='#'){
      grid[y][x] = '.';

      int s1 = s.sz;
      s.insert(P(y,x));
      int s2 = s.sz;
      s.erase(P(y,x));
      if(s1==s2){
	q.push(P(y,x));
	
	while(q.size()){
	  int y = q.top().first, x = q.top().second;
	  q.pop();
	  
	  if(grid[y][x] == 't'){
	    cout << i+1 << endl;
	    return 0;
	  }
	  
	  vis[y][x] = true;
	  int dy[] = {-1,0,1,0},dx[] = {0,1,0,-1};
	  
	  For(i,4){
	    int sy = y + dy[i] , sx = x + dx[i];
	    if(sy<0 || sx<0 || h<=sy || w<=sx)continue;
	    if(vis[sy][sx])continue;
	    if(grid[sy][sx] == '#'){
	      s.insert(P(sy,sx));
	      continue;
	    }
	    q.push(P(sy,sx));
	  }
	}
      }
    }
  }

  cout << -1 << endl;
  return 0;
}