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;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

template<class T> constexpr bool in_range(T y, T x, T H, T W) { return 0<=y&&y<H&&0<=x&&x<W; }

template<class T> using PQ_G = priority_queue<T, vector<T>, greater<T>>;

typedef long long ll;
int const inf = 1<<29;

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

int main() {

  int H, W; cin>> W >> H;
  vector<string> G(H);
  rep(i, H) cin >> G[i];

  int N; cin >> N;
  map<pair<int, int>, int> mp;

  rep(i, N) {
    int x, y; cin >> x >> y;
    mp[{y, x}] = i + 1;
  }
  
  PQ_G<tuple<int, int, int>> q;
  q.emplace(0, 0, 0);

  static int dist[1001][1001];
  rep(i, 1001) rep(j, 1001) dist[i][j] = inf;

  dist[0][0] = 0;

  while(!q.empty()) {
    int cost, y, x; tie(cost, y, x) = q.top(); q.pop();

    if(dist[y][x] < cost) continue;

    if(G[y][x] == 't') {
      cout << cost << endl;
      exit(0);
    }

    rep(k, 4) {
      int ny = y + dy[k], nx = x + dx[k];
      if(!in_range(ny, nx, H, W)) continue;
      if(G[ny][nx] == '#') {
        if(mp.find({ny, nx}) != mp.end()) {
          int ncost = max(mp[{ny, nx}], cost);
          if(dist[ny][nx] <= ncost) continue;
          dist[ny][nx] = ncost;
          q.emplace(ncost, ny, nx);
        }
      }
      else {
        if(dist[ny][nx] <= cost) continue;
        dist[ny][nx] = cost;
        q.emplace(cost, ny, nx);
      }
    }
  }

  cout << -1 << endl;

  return 0;
}