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 <fstream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <functional>
using namespace std;
template<typename T> void setmin(T& a, T& b) { a = min(a, b); }
template<typename T> void setmax(T& a, T& b) { a = max(a, b); }

const int INF = 1 << 25;

int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
char b[1000][1000];
int open[1000][1000];
int d[1000][1000];
int H, W, N, tx, ty;
typedef pair<int, int> Pii;
typedef pair<int, Pii> P;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef _WIN32
	istream &cin = ifstream("case.txt");
#endif

	while(cin >> W >> H) {
		for(int y = 0; y < H; y++) {
			for(int x = 0; x < W; x++) {
				cin >> b[y][x];
				if(b[y][x] == 't') {
					tx = x, ty = y;
				}
				d[y][x] = INF;
				open[y][x] = b[y][x] == '#' ? INF : 0;
			}
		}

		cin >> N;
		for(int i = 0; i < N; i++) {
			int x, y;
			cin >> x >> y;
			if(b[y][x] == '#') open[y][x] = i + 1;
		}

		d[0][0] = 0;
		priority_queue<P, vector<P>, greater<P> > q;
		q.push(P(0, Pii(0, 0)));
		while(!q.empty()) {
			int cost = q.top().first;
			int x = q.top().second.first, y = q.top().second.second;
			q.pop();
			if(d[y][x] != cost) continue;
			if(x == tx && y == ty) break;
			for(int k = 0; k < 4; k++) {
				int nx = x + dx[k], ny = y + dy[k];
				if(0 <= nx && nx < W && 0 <= ny && ny < H) {
					if(b[ny][nx] == '#') {
						if(d[ny][nx] > max(d[y][x], open[ny][nx])) {
							d[ny][nx] = max(d[y][x], open[ny][nx]);
							q.push(P(d[ny][nx], Pii(nx, ny)));
						}
					}
					else if(d[ny][nx] > d[y][x]) {
						d[ny][nx] = d[y][x];
						q.push(P(d[ny][nx], Pii(nx, ny)));
					}
				}
			}
		}

		if(d[ty][tx] == INF) {
			cout << -1 << endl;
		}
		else {
			cout << d[ty][tx] << endl;
		}
	}
}