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 <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>

using namespace std;

const double EPS=(1e-10);
typedef long long ll;
typedef pair<int,int> pii;
bool EQ(double a,double b){
  return abs((a)-(b))<EPS;
}
void fast_stream(){
	std::ios_base::sync_with_stdio(0);
}

int W,H;
int N;
char field[1001][1001];
int gx,gy;
bool passed[1001][1001];
int nodeNum[1001][1001];

const int dy[]={-1,0,0,1};
const int dx[]={0,-1,1,0};
int setSize;

class UnionFindTree{

private:
  // indexツづ個青板づ個親ツノツーツド
  vector<int> par;
  // indexツづーツ債ェツづつキツづゥツ姪伉づ個δ可δ督ク
  vector<int> rank;
  // ツ姪伉づ個催妥・ツ値
  int treeSize;
public:
    UnionFindTree(int initTreeSize = 1000){
        // ツ暗クツ青板づ与ツつヲツづァツづェツつスツ値ツづーツ催妥・ツ格ツ納ツ青板づつキツづゥUnionFindTreeツづ個催ャツ青ャ
        treeSize = initTreeSize;
        init();
    }
    void init(){
        for(int i = 0; i < treeSize; i++){
            par.push_back(i);
            rank.push_back(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[y] == rank[x]){
                rank[x]++;
            }
        }
    }
    bool same(int x,int y){
        return find(x) == find(y);
    }

};

void solve(){
    cin>>W>>H;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin>>field[i][j];
            if(field[i][j]=='t'){
                field[i][j]='.';
                gx=j;gy=i;
            }
        }
    }
    UnionFindTree uft(H*W);
    for(int i=0;i<H;i++)for(int j=0;j<W;j++)nodeNum[i][j]=i*W+j;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(field[i][j]=='.'){
                if(j-1>=0&&field[i][j-1]=='.')uft.unite(i*W+j,i*W+j-1);
                if(i-1>=0&&field[i-1][j]=='.')uft.unite(i*W+j,(i-1)*W+j);
            }
        }
    }
    cin>>N;
    bool ok=false;
    if(uft.same(nodeNum[0][0],nodeNum[gy][gx])){
        cout<<0<<endl;
        for(int i=0;i<N;i++){
            int x,y;
            cin>>x>>y;
        }
    }
    else{
        for(int i=0;i<N;i++){
            int x,y;
            cin>>x>>y;
            if(ok)continue;
            if(field[y][x]=='.')continue;
            field[y][x]='.';
            vector<int> vp;
            for(int j=0;j<4;j++){
                int ny=y+dy[j];
                int nx=x+dx[j];
                if(ny>=0&&nx>=0&&ny<H&&nx<W&&field[ny][nx]=='.')vp.push_back(nodeNum[ny][nx]);
            }
            for(int j=0;j<vp.size();j++)uft.unite(nodeNum[y][x],vp[j]);
            if(uft.same(nodeNum[0][0],nodeNum[gy][gx])){
                ok=true;
                cout<<i+1<<endl;
                continue;
            }
        }
        if(!ok)cout<<-1<<endl;
    }
}


int main(){

    solve();

    return 0;
}