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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CLEAR(arr, val) memset(arr, val, sizeof(arr))

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
bool valid_pos(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

int main()
{
	ios::sync_with_stdio(false);

	int w, h;
	cin >> w >> h;
	static char s[1024][1024];
	for (int i = 0; i < h; ++i)
		cin >> s[i];

	int n;
	cin >> n;
	int wx[1024], wy[1024];
	wx[0] = wy[0] = 0;
	for (int i = 1; i <= n; ++i)
		cin >> wx[i] >> wy[i];

	int res = -1;
	static bool visit[1024][1024];
	visit[0][0] = true;
	for (int t = 0; t <= n && res == -1; ++t)
	{
		s[wy[t]][wx[t]] = '.';
		if (!visit[wy[t]][wx[t]])
			continue;

		queue<pint> q;
		q.push(pint(wx[t], wy[t]));
		while (!q.empty())
		{
			pint c = q.front(); q.pop();
			int x = c.first, y = c.second;
			if (s[y][x] == '#')
				continue;
			else if (s[y][x] == 't')
			{
				res = t;
				break;
			}

			for (int i = 0; i < 4; ++i)
			{
				int tx = x + dx[i], ty = y + dy[i];
				if (valid_pos(tx, ty, w, h) && !visit[ty][tx])
				{
					visit[ty][tx] = true;
					q.push(pint(tx, ty));
				}
			}
		}
	}
	cout << res << endl;
}