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 rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
 
typedef int Weight;;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src_, int dst_, Weight w_) :
        src(src_), dst(dst_), weight(w_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
 
const int inf = 1e8;
 
char g[1010][1010];
int open[1010][1010];
int n,h,w;
int vis[1010][1010];
 
bool check(int lim){
    rep(i,h)rep(j,w) vis[i][j] = false;
    vector<pair<int,int>> S = { { 0,0 } };
    while(S.size()){
        int ci,cj;
        tie(ci,cj) = S.back();
        S.pop_back();
        //cout << ci << " " << cj << endl;
        vis[ci][cj] = true;
        if(g[ci][cj] == 't') return true;
        int ds[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        for(auto & d : ds){
            int ni = ci + d[0];
            int nj = cj + d[1];
            if(ni >= h || nj >= w || ni < 0 || nj < 0) continue;
            if(vis[ni][nj]) continue;
            if(g[ni][nj] == '.' || g[ni][nj] == 't' || (g[ni][nj] == '#' && open[ni][nj] <= lim)){
                S.emplace_back(ni,nj);
            }
        }
    }
    return false;
}

int solve(){
    int l = -1, r = n+10;
    // xxxxoooo
    //    lr
    while(l+1 < r){
        int m = (l+r)/2;
        if(check(m)) r = m;
        else l = m;
    }
    if(r > n) return -1;
    else return r;
}

int main(){
    while(cin >> w >> h && w){
        rep(i,h) cin >> g[i];
        rep(i,h)rep(j,w) open[i][j] = inf;
        cin >> n;
        rep(i,n){
            int x,y;
            cin >> x >> y;
            open[y][x] = i+1;
        }
        cout << solve() << endl;
    }
}