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:
//17
#include<iostream>
#include<algorithm>
#include<queue>
#include<utility>
#include<set>

using namespace std;

char g[1000][1001];
int w,h;
set<pair<int,int> > s;

bool ff(pair<int,int> p){
  bool r=false;
  if(s.count(p)){
    queue<pair<int,int> > que;
    que.push(p);
    while(!que.empty()){
      int x=que.front().first;
      int y=que.front().second;
      que.pop();
      if(x<0||w<=x||y<0||h<=y||g[y][x]=='p'){
	continue;
      }else if(g[y][x]=='#'){
	s.insert(make_pair(x,y));
      }else{
	r|=g[y][x]=='t';
	g[y][x]='p';
	for(int i=0;i<4;i++){
	  const static int d[]={0,1,0,-1,0};
	  que.push(make_pair(x+d[i],y+d[i+1]));
	}
      }
    }
  }
  return r;
}

int main(){
  cin>>w>>h;
  for(int i=0;i<h;i++){
    cin>>g[i];
  }
  s.insert(make_pair(0,0));
  int t=-1;
  if(ff(make_pair(0,0))){
    t=0;
  }
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    int x,y;
    cin>>x>>y;
    g[y][x]='.';
    if(ff(make_pair(x,y))){
      t=i;
    }
  }
  cout<<t<<endl;
  return 0;
}