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"

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int par[1000010];
int Rank[1000010];

void init(int n){
    rep(i,n){
        par[i]=i;
        Rank[i]=0;
    }
}

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

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    
    if(Rank[x]<Rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(Rank[x]==Rank[y])Rank[x]++;
    }
}



int main(){
    int dx[]={0,1,0,-1};
    int dy[]={1,0,-1,0};
    string data[1100];
    int w,h;
    cin>>w>>h;
    rep(i,h)cin>>data[i];
    int gy=0,gx=0;
    rep(i,h){
        rep(j,w){
            if(data[i][j]=='t')gy=i,gx=j;
        }
    }
    init(w*h);
    rep(i,h){
        rep(j,w){
            if(data[i][j]!='#'){
                rep(k,4){
                    int ddx=j+dx[k],ddy=i+dy[k];
                    if(ddx>=0&&ddx<w&&ddy>=0&&ddy<h&&data[ddy][ddx]!='#'){
                        unite(i*w+j,ddy*w+ddx);
                    }
                }
            }
        }
    }
    int n;
    cin>>n;
    int ans=-1;
    rep(i,n){
        if(find(0)==find(gy*w+gx)&&ans==-1){
            ans=i;
        }
        int x,y;
        cin>>x>>y;
        data[y][x]='.';
        int ddx[5],ddy[5];
        rep(k,4){
            ddx[k]=x+dx[k];
            ddy[k]=y+dy[k];
        }
        ddx[4]=x;
        ddy[4]=y;
        rep(k,5){
            if(ddx[k]<0||ddx[k]>=w||ddy[k]<0||ddy[k]>=h||data[ddy[k]][ddx[k]]=='#')continue;
            rep(l,5){
                if(k==l)continue;
                if(ddx[l]<0||ddx[l]>=w||ddy[l]<0||ddy[l]>=h||data[ddy[l]][ddx[l]]=='#')continue;
//                cout<<ddy[k]<<" "<<ddx[k]<<" "<<ddy[l]<<" "<<ddx[l]<<endl;
                unite(ddy[k]*w+ddx[k],ddy[l]*w+ddx[l]);
            }
        }
    }
    if(find(0)==find(gy*w+gx)&&ans==-1)
        ans=n;

    cout<<ans<<endl;
}