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<stack>
#include<map>
using namespace std;

#define N 1000

#define id(x,y) ((y)*(N+2)+(x))
int parent[(N+2)*(N+2)];
class UnionFind {
	
public:
	void init() {
		for(int i=0; i<N+2; ++i) {
			for(int j=0; j<N+2; ++j) {
				parent[id(j,i)] = id(j,i);
			}
		}
	}
	int find(int x) {
		if(parent[x]==x) return x;
		return parent[x] = find(parent[x]);
	}
	void unite(int x, int y) {
		if(find(x)==find(y)) return;
		if(find(x)<find(y)) {
			parent[find(y)] = parent[find(x)];
		}else {
			parent[find(x)] = parent[find(y)];
		}
	}
	bool alone(int x) {
		return find(x)==x;
	}
	bool same(int x, int y) {
		return find(x)==find(y);
	}
};

typedef pair<int, int> P;

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

int main() {
	int w, h, tx[1000], ty[1000], gx, gy, n, ans;
	char map[N+2][N+2];
	UnionFind uf;
	stack<P> s;
	while(cin >> w >> h) {
		for(int i=0; i<h+2; ++i) for(int j=0; j<w+2; ++j) map[i][j] = '#';
		for(int i=1; i<=h; ++i) {
			for(int j=1; j<=w; ++j) {
				cin >> map[i][j];
				if(map[i][j]=='t') {
					gx = j; gy = i;
				}
			}
		}
		uf.init();
		for(int i=1; i<=h; ++i) {
			for(int j=1; j<=w; ++j) {
				if(map[i][j]!='#'&&uf.alone(id(j,i))) {
					s.push(P(j, i));
					while(!s.empty()) {
						int x = s.top().first, y = s.top().second; s.pop();
						for(int k=0; k<4; ++k) {
							if(map[y+dy[k]][x+dx[k]]!='#'&&!uf.same(id(x,y), id(x+dx[k],y+dy[k]))) {
								uf.unite(id(x,y), id(x+dx[k],y+dy[k]));
								s.push(P(x+dx[k],y+dy[k]));
							}
						}
					}
				}				
			}
		}
		ans = -1;
		cin >> n;
		for(int i=0; i<n; ++i) {
			cin >> tx[i] >> ty[i];
			tx[i]++; ty[i]++;
		}
		if(uf.same(id(1,1), id(gx,gy))) ans = 0;
		else for(int i=0; i<n; ++i) {
			if(map[ty[i]][tx[i]]!='#') continue;
			map[ty[i]][tx[i]] = '.';
			for(int k=0; k<4; ++k) {
				if(map[ty[i]+dy[k]][tx[i]+dx[k]]!='#') {
					uf.unite(id(tx[i],ty[i]), id(tx[i]+dx[k],ty[i]+dy[k]));
				}
			}
			if(uf.same(id(1,1), id(gx,gy))) {
				ans = i+1; break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}