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:
#ifndef ___Rank_Union_Find
#define ___Rank_Union_Find

// ------ Required ------ //
#include <vector>

// ------ Class ------ //
class RankUnionFind {
private:
	int size_; std::vector<int> par, rank;
public:
	RankUnionFind() : size_(0), par(std::vector<int>()), rank(std::vector<int>()) {};
	RankUnionFind(int size__) : size_(size__) {
		par.resize(size_); rank.resize(size_);
		for (int i = 0; i < size_; i++) par[i] = i, rank[i] = 0;
	}
	int size() { return size_; }
	int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
	bool same(int x, int y) { return root(x) == root(y); }
	void unite(int x, int y) {
		x = root(x), y = root(y);
		if (x == y) return;
		if (rank[x] < rank[y]) par[x] = y;
		else if (rank[x] == rank[y]) par[y] = x, rank[x]++;
		else par[y] = x;
	}
	bool operator==(const RankUnionFind &u) { return par == u.par; }
	bool operator!=(const RankUnionFind &u) { return par != u.par; }
};

#endif

#include <cstdio>
#pragma warning(disable : 4996)
int H, W, Q, x, y, v; char s[1007][1007];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
int main() {
	scanf("%d%d", &W, &H);
	for (int i = 0; i < H; i++) scanf("%s", s[i]);
	RankUnionFind uf(W * H);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (s[i][j] == 't') v = i * W + j;
			if (s[i][j] == '#') continue;
			for (int k = 0; k < 2; k++) {
				int tx = j + k, ty = i + 1 - k;
				if (0 <= tx && tx < W && 0 <= ty && ty < H && s[ty][tx] != '#') {
					uf.unite(i * W + j, ty * W + tx);
				}
			}
		}
	}
	scanf("%d", &Q);
	int ret = -1;
	if (uf.same(0, v)) ret = 0;
	else {
		for (int i = 0; i < Q; i++) {
			scanf("%d%d", &x, &y); s[y][x] = '.';
			for (int j = 0; j < 4; j++) {
				int tx = x + dx[j], ty = y + dy[j];
				if (0 <= tx && tx < W && 0 <= ty && ty < H && s[ty][tx] != '#') {
					uf.unite(y * W + x, ty * W + tx);
				}
			}
			if (uf.same(0, v)) {
				ret = i + 1; break;
			}
		}
	}
	printf("%d\n", ret);
	return 0;
}