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 <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

struct UnionFind
{
	vector<int> par;
	UnionFind(int n) :par(n, -1) {}
	int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
	void unite(int x, int y)
	{
		x = find(x); y = find(y);
		if (x == y) return;
		if (par[y] < par[x]) swap(x, y);
		if (par[x] == par[y]) par[x]--;
		par[y] = x;
		if (find(x) != find(y)) par[find(y)] = x;
	}
	int count()
	{
		int cnt = 0;
		REP(i, par.size()) if (par[i] < 0) cnt++;
		return cnt;
	}
	bool same(int x, int y)
	{
		return find(x) == find(y);
	}
};

const int dx[] = { -1, 0, 0, 1 }, dy[] = { 0, -1, 1, 0 };
//[const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

int main()
{
	int w, h;
	cin >> w >> h;
	vs fld(h);
	REP(i, h) cin >> fld[i];
	int gx, gy;
	REP(i, h)REP(j, w)
	{
		if (fld[i][j] == 't')
		{
			fld[i][j] = '.';
			gx = i, gy = j;
		}
	}
	int gp = place(gx, gy, w);
	int n; cin >> n;
	vector<pii> v;
	REP(i, n)
	{
		int a, b; cin >> a >> b;
		v.emplace_back(b, a);
	}
	int lb = -1, ub = n + 1;
	while (ub - lb > 1)
	{
		int mid = (lb + ub) / 2;
		vs cp = fld;
		REP(i, mid)
		{
			int a = v[i].first, b = v[i].second;
			cp[a][b] = '.';
		}
		UnionFind uf(h*w);
		REP(i, h)REP(j, w)
		{
			if (cp[i][j] == '#') continue;
			REP(k, 4)
			{
				int nx = i + dx[k], ny = j + dy[k];
				if (!valid(nx, ny, h, w) || cp[nx][ny]=='#') continue;
				uf.unite(place(i, j, w), place(nx, ny, w));
			}
		}
		if (uf.same(0, gp)) ub = mid;
		else lb = mid;
	}
	if (lb == n) puts("-1");
	else cout << lb + 1 << endl;
	return 0;
}