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>
#define r(i,n) for(int i=0;i<n;i++)
#define mk make_pair
using namespace std;
int n,m,h,w,x2,y2;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
string s[1001];
bool b[1001][1001];
bool bfs(int y3,int x3){
  int y=0,x=0;
  b[0][0]=1;
  queue<pair<int,int> >q;
  q.push(mk(x3,y3));
  while(!q.empty()){
    pair<int,int>p=q.front();q.pop();
    int xx=p.first,yy=p.second;
    r(i,4){
      int x1=xx+dx[i],y1=yy+dy[i];
      if(x1<0||y1<0||x1>=w||y1>=h)continue;
      if(!b[y1][x1]&&s[y1][x1]!='#'){
	if(s[y1][x1]=='t')return 1;
	b[y1][x1]=1;
	q.push(mk(x1,y1));
      }
      else b[y1][x1]=1;
    }
  }
  return 0;
}
int main(){
  cin>>w>>h;
  r(i,h)cin>>s[i];
  cin>>m;
  if(bfs(0,0)){
    cout<<0<<endl;
    return 0;
  }
  r(i,m){
    cin>>x2>>y2;
    if(s[y2][x2]=='.')continue;
    s[y2][x2]='.';
    if(b[y2][x2])if(bfs(y2,x2)){
      cout<<i+1<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
}