Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

10 10
.....#....
.....#....
.....#....
######....
..........
####......
....###...
t..#..####
...##.....
....#...##
3
0 3
0 5
4 6


Output

2
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> P;   // x, y
typedef pair<P, int> PP;    // x, y, step
static const int INF = 1e9;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};

void solve()
{
	int W, H;
	cin >> W >> H;
	vector< vector<char> > field(H, vector<char>(W));
	vector< vector<int> > step(H, vector<int>(W));
	P goal;
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			cin >> field[i][j];
			if (field[i][j] == 't')
			{
				goal.first = j;
				goal.second = i;
			}
			step[i][j] = INF;
		}
	}
	int N;
	cin >> N;
	vector<P> release(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> release[i].first >> release[i].second;
	}
	step[0][0] = 0;
	queue<PP> que;
	que.push(make_pair(make_pair(0, 0), 1));
	int time = 0;
	for (int i = -1; i < N; ++i)
	{
		if (i >= 0)
		{
			++time;
			field[release[i].second][release[i].first] = '.';
			int minStep = INF;
			for (int j = 0; j < 4; ++j)
			{
				int x = release[i].first + dx[j];
				int y = release[i].second + dy[j];
				if (0 <= x && x < W && 0 <= y && y < H && step[y][x] < minStep)
				{
					minStep = step[y][x];
					step[release[i].second][release[i].first] = minStep + 1;
				}
			}
			if (minStep != INF)
			{
				que.push(make_pair(make_pair(release[i].first, release[i].second), minStep + 1));
			}
		}
		while (!que.empty())
		{
			PP pp = que.front();
			que.pop();
			if (pp.first.first == goal.first && pp.first.second == goal.second)
			{
				cout << time << endl;
				return;
			}
			for (int j = 0; j < 4; ++j)
			{
				int nx = pp.first.first + dx[j];
				int ny = pp.first.second + dy[j];
				if (0 <= nx && nx < W && 0 <= ny && ny < H && field[ny][nx] != '#' && step[ny][nx] == INF)
				{
					step[ny][nx] = pp.second;
					que.push(make_pair(make_pair(nx, ny), pp.second + 1));
				}
			}
		}
	}
	cout << -1 << endl;
}

int main()
{
	solve();
	return(0);
}