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 <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

char ba[1000][1000];
int dist[1000][1000];
int aku[1000][1000];
struct P {
  int x,y;
  int t;
  P(int y, int x, int t) : y(y),x(x),t(t) {}
};

bool operator<(const P &a, const P &b) {
  return a.t > b.t;
}

int main() {
  int w,h;
  cin >> w >> h;
  priority_queue<P> Q;
  REP(i,h) {
    REP(j,w) {
      cin >> ba[i][j];
    }
  }
  int n;
  cin >> n;
  memset(aku,0,sizeof(aku));
  REP(i, h) {
    REP(j, w) {
      if (ba[i][j] == '#') aku[i][j] = INF;
    }
  }
  REP(i, n) {
    int x, y;
    cin >> x >> y;
    aku[y][x] = i+1;
  }
  
  Q.push(P(0,0,0));
  REP(i,h) REP(j,w) dist[i][j] = INF;
  dist[0][0] = 0;
  int dy[] = {-1,0,1,0};
  int dx[] = {0,1,0,-1};
  int ans = -1;
  while(!Q.empty()) {
    P p = Q.top(); Q.pop();
    if (dist[p.y][p.x] < p.t) continue;
    
    if (ba[p.y][p.x] == 't') {
      ans = p.t;
      break;
    }
    
    REP(i, 4) {
      int yy = p.y+dy[i];
      int xx = p.x+dx[i];
      
      if (yy<0||yy>=h||xx<0||xx>=w) continue;
      int d = max(aku[yy][xx], dist[p.y][p.x]);
      if (d == INF) continue;
      if (dist[yy][xx] > d) {
	dist[yy][xx] = d;
	Q.push(P(yy,xx,d));
      } 
    }
  }
  cout << ans << endl;
}