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<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

vector<ll> dx={1,0,-1,0};
vector<ll> dy={0,1,0,-1};


int main(){
    ll w,h;
    cin>>w>>h;
    vector<string> A(h);
    for(auto &I:A){cin>>I;}
    vector<vector<bool>> can(h,vector<bool>(w,false));
    pll G;
    for(int i=0;i<h;i++){
        for(int t=0;t<w;t++){
            if(A[i][t]=='t'){G={i,t};}
        }
    }
    queue<pll> Q;
    Q.push({0,0});
    can[0][0]=true;
    while(!Q.empty()){
        pll W=Q.front(); Q.pop();
        for(int i=0;i<4;i++){
            ll X=W.F+dx[i];
            ll Y=W.S+dy[i];
            if(X<0 || Y<0 || X>=h || Y>=w || can[X][Y] || A[X][Y]=='#'){continue;}
            can[X][Y]=true;
            Q.push({X,Y});
        }
    }
    if(can[G.F][G.S]){cout<<0<<endl; return 0;}
    ll n;
    cin>>n;
    for(int T=1;T<=n;T++){
        ll x,y;
        cin>>x>>y;
        swap(x,y);
        if(A[x][y]=='#'){
            A[x][y]='.';
            for(int i=0;i<4;i++){
                ll X=x+dx[i];
                ll Y=y+dy[i];
                if(X<0 || Y<0 || X>=h || Y>=w || !can[X][Y] || A[X][Y]=='#'){continue;}
                Q.push({x,y});
                can[x][y]=true;
                break;
            }
            while(!Q.empty()){
                pll W=Q.front(); Q.pop();
                for(int i=0;i<4;i++){
                    ll X=W.F+dx[i];
                    ll Y=W.S+dy[i];
                    if(X<0 || Y<0 || X>=h || Y>=w || can[X][Y] || A[X][Y]=='#'){continue;}
                    can[X][Y]=true;
                    Q.push({X,Y});
                }
            }
        }
        if(can[G.F][G.S]){cout<<T<<endl; return 0;}
    }
    cout<<-1<<endl;
    
    
    return 0;
}