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 <vector>
#include <queue>
using namespace std;

bool ok(const vector<string>& grid, const vector<vector<int> >& m, int t)
{
  const int H = grid.size(), W = grid[0].size();
  vector<vector<int> > visited(H, vector<int>(W, false));
  visited[0][0] = true;
  queue<pair<int,int> > q;
  q.push(make_pair(0, 0));
  while (!q.empty()) {
    const int x = q.front().first;
    const int y = q.front().second;
    q.pop();
    if (grid[x][y] == 't') {
      return true;
    }
    for (int d = 0; d < 4; d++) {
      static const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
      const int z = x + dx[d], w = y + dy[d];
      if (0 <= z && z < H && 0 <= w && w < W
          && !visited[z][w]
          && (grid[z][w] != '#' || m[z][w] <= t)) {
        visited[z][w] = true;
        q.push(make_pair(z, w));
      }
    }
  }
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  int W, H;
  cin >> W >> H;
  vector<string> grid(H);
  for (int i = 0; i < H; i++) {
    cin >> grid[i];
  }
  int N;
  cin >> N;
  static const int INF = 10000000;
  vector<vector<int> > m(H, vector<int>(W, INF));
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    m[y][x] = i+1;
  }

  if (!ok(grid, m, N)) {
    cout << "-1" << endl;
    return 0;
  }

  int lo = 0, hi = N;
  while (lo < hi) {
    const int mid = (lo + hi)/2;
    if (ok(grid, m, mid)) {
      hi = mid;
    } else {
      lo = mid+1;
    }
  }
  cout << lo << endl;
  return 0;
}