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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair

using namespace std;

typedef pair<int, int> P;

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

vector<P> open;
int W, H, N;
char field[1002][1002];

bool visit[1002][1002];
bool check(int n){
	memset(visit, 0, sizeof(visit));

	rep(i, min(n, (int)open.size())){
		field[open[i].second][open[i].first] = '.';
	}
	for(int i = n; i < open.size(); i++){
		field[open[i].second][open[i].first] = '#';
	}

	//cout << n << endl;
	//rep(i, 10){
	//	rep(j, 10){
	//		cout << field[i][j];
	//	}cout << endl;
	//}cout << endl;

	queue<P> q;
	q.push(MP(0, 0));

	while(!q.empty()){
		P p = q.front();
		q.pop();
		
		if(visit[p.second][p.first]) continue;
		visit[p.second][p.first] = true;

		if(field[p.second][p.first] == 't') return true;

		rep(i, 4){
			int nx = p.first+dx[i], ny = p.second+dy[i];
			if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
			if(field[ny][nx] != '#') q.push(MP(nx, ny));
		}
	}

	return false;
}


int main(){
	cin >> W >> H;
	rep(i, H) rep(j, W) cin >> field[i][j];
	cin >> N;
	rep(i, N){
		int x, y;
		cin >> x >> y;
		if(field[y][x] != '#'){
			x = y = 1001;
		}
		open.push_back(MP(x, y));
	}

	int lb = -1, ub = 10000;
	while(ub - lb > 1){
		int mid = (lb+ub)/2;
		if(check(mid))ub = mid;
		else lb = mid;
	}
	cout << (ub>N?-1:ub) << endl;

	return 0;
}