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 <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
//C++11
#if __cplusplus == 201103L
#include <tuple>
#endif

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
typedef pair<int, int> P;

int main(){
  int W, H, T, ax, ay;
  while(cin>>W>>H && H){
    vector<string> grid(H);
    REP(i, H)cin>>grid[i];
    int time[1000][1000] = {};
    REP(y, H)REP(x, W){
      if(grid[y][x] == '#'){
        time[y][x] = INF;
      }
      if(grid[y][x] == 't'){
        ax = x, ay = y;
      }
    }
    cin>>T;
    REP(i, T){
      int x, y;
      cin>>x>>y;
      time[y][x] = min(time[y][x], i + 1);
    }
    int ans[1000][1000];
    REP(y, H)REP(x, W) ans[y][x] = INF;
    ans[0][0] = 0;
    queue<P> que;
    que.push(P(0, 0));
    while(!que.empty()){
      P p = que.front(); que.pop();
      int x = p.first, y = p.second;
      int dx[4] = {1, 0, -1, 0};
      int dy[4] = {0, 1, 0, -1};
      REP(r, 4){
        int nx = x + dx[r], ny = y + dy[r];
        if(nx >= 0 && nx < W && ny >= 0 && ny < H && time[ny][nx] != INF){
          int nexttime = max(time[ny][nx], ans[y][x]);
          if(nexttime < ans[ny][nx]){
            ans[ny][nx] = nexttime;
            que.push(P(nx, ny));
          }
        }
      }
    }
    if(ans[ay][ax] == INF) ans[ay][ax] = -1;
    cout<<ans[ay][ax] << endl;
  }
  return 0;
}