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 <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

const int xdir[4] = {0, 1, 0, -1};
const int ydir[4] = {1, 0, -1, 0};

int w, h;
bool vis[1001][1001];
int a[1001][1001];

class St{
public:
  int x, y, s;

  St() {}
  St(int _x, int _y, int _s): x(_x), y(_y), s(_s) {}

  bool operator>(const St& st) const {
    return s > st.s;
  }

  bool operator<(const St& st) const {
    return s < st.s;
  }
};

int bfs()
{
  priority_queue<St, vector<St>, greater<St> > que;
  que.push(St(0, 0, 0));
  fill(&vis[0][0], &vis[h][0], true);
  vis[0][0] = false;
  St st;
  int dy, dx;

  while(!que.empty()){
    st = que.top();
    que.pop();

    if(a[st.y][st.x] == -2) return st.s;

    for(int i = 0; i < 4; ++i){
      dy = st.y+ydir[i];
      dx = st.x+xdir[i];
      if(0 <= dx && dx < w && 0 <= dy && dy < h && vis[dy][dx] && a[dy][dx] != -1){
	vis[dy][dx] = false;
	que.push(St(dx, dy, max(st.s, a[dy][dx])));
      }
    }
  }

  return -1;
}

int main()
{
  int m, x, y;
  char ch;

  while(cin>>w>>h && h+w){
    for(int i = 0; i < h; ++i)
      for(int j = 0; j < w; ++j){
	cin >> ch;
	if(ch == 't') a[i][j] = -2;
	if(ch == '.') a[i][j] = 0;
	if(ch == '#') a[i][j] = -1;
      }

    cin >> m;
    for(int i = 1; i <= m; ++i){
      cin >> x >> y;
      if(a[y][x] == -1) a[y][x] = i;
    }

    cout << bfs() << endl;
  }

  return 0;
}