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:
// template {{{

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vvd = vector<vd>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<double, double>;
using tp = tuple<int, int, int>;
using tp4 = tuple<int, int, int, int>;
using tp5 = tuple<int, int, int, int, int>;

template<typename T>
using max_pq = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

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

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(std::begin(c), std::end(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(std::begin(c), std::end(c)); }

template<typename T>
inline void unique(T &c){ std::sort(std::begin(c), std::end(c)); c.erase(std::unique(all(c)), std::end(c)); }

// }}}

int w, h;
char g[1024][1024];
int dist[1024][1024];

void bfs(int x, int y, int d)
{
	queue<pi> q;
	dist[x][y] = d;
	q.emplace(x, y);
	while (q.size()){
		int x, y;
		tie(x, y) = q.front(); q.pop();
		rep(i, 4){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (g[nx][ny] == '#') continue;
			if (~dist[nx][ny]) continue;
			dist[nx][ny] = d;
			q.emplace(nx, ny);
		}
	}
}

int main()
{
	memset(g, '#', sizeof(g));
	memset(dist, -1, sizeof(dist));
	cin >> w >> h;
	int *p;
	rep(i, h) rep(j, w){
		cin >> g[i + 1][j + 1];
		if (g[i + 1][j + 1] == 't'){
			p = &dist[i + 1][j + 1];
		}
	}
	
	bfs(1, 1, 0);

	int n;
	cin >> n;
	rep(i, n){
		int x, y;
		cin >> y >> x, x++, y++;
		if (g[x][y] == '#'){
			g[x][y] = '.';
			bool f = false;
			rep(j, 4){
				if (~dist[x + dx[j]][y + dy[j]]) f = true;
			}
			if (f) bfs(x, y, i + 1);
		}
	}
	
	cout << *p << endl;
}