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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;


struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main() {
	int W,H;cin>>W>>H;
	vector<vector<int>>field(H+2,vector<int>(W+2,1));
	int gx,gy;
	for (int i = 0; i < H; ++i) {
		string st;cin>>st;
		for (int j = 0; j < W; ++j) {
			if (st[j] == '#') {
				
			}
			else if (st[j] == '.') {
				field[i+1][j+1]=0;
			}
			else if (st[j] == 't') {
				field[i+1][j+1]=0;
				gx=j+1;
				gy=i+1;
			}
		}
	}

	int start_id=W+3;
	int goal_id(gy*(W+2)+gx);
	UnionFind uf((H+2)*(W+2));
	int dx[] = { -1,0,1,0 };
	int dy[] = { 0,1,0,-1 };
	for (int y = 1; y <= H; ++y) {
		for (int x = 1; x <= W; ++x) {
			const int now_y=y;
			const int now_x=x;
			const int now_id=((W+2)*now_y+now_x);
			for (int way = 0; way < 4; ++way) {
				const int next_y=now_y+dy[way];
				const int next_x=now_x+dx[way];
				const int next_id=((W+2)*next_y+next_x);

				if (!field[next_y][next_x] && !field[now_y][now_x]) {
					uf.unionSet(now_id,next_id);
				}
			}
		}
	}

	int ans=-1;
	{
		if (uf.root(start_id) == uf.root(goal_id)) {
			ans=0;
		}
		else {
			int N; cin >> N;
			for (int i = 0; i < N; ++i) {
				int x, y; cin >> x >> y;
				int now_y(y + 1);
				int now_x(x + 1);
				const int now_id = ((W + 2)*now_y + now_x);
				field[now_y][now_x] = 0;
				for (int way = 0; way < 4; ++way) {
					const int next_y = now_y + dy[way];
					const int next_x = now_x + dx[way];
					const int next_id = ((W + 2)*next_y + next_x);

					if (!field[next_y][next_x] && !field[now_y][now_x]) {
						uf.unionSet(next_id,now_id);
					}
				}
				if (uf.root(start_id) == uf.root(goal_id)) {
					ans=i+1;
					break;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}