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 <queue>
#include <map>

using namespace std;

int W, H, N;
vector<string> board;
vector<vector<bool>> visit;

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

bool Search(int x, int y)
{
    if (board[y][x] == '#')
        board[y][x] = '.';

    if (!visit[y][x])
        return false;

    queue<pair<int, int>> que;
    que.push(make_pair(x, y));

    while (!que.empty()) {
        pair<int, int> now = que.front();
        que.pop();

        if (board[now.second][now.first] == 't')
            return true;

        for (int d = 0; d < 4; ++d) {
            int nx = now.first + dx[d];
            int ny = now.second + dy[d];

            if (nx < 0 || nx >= W || ny < 0 || ny >= H)
                continue;
            if (visit[ny][nx])
                continue;

            visit[ny][nx] = true;

            if (board[ny][nx] != '#')
                que.push(make_pair(nx, ny));
        }
    }

    return false;
}

int main()
{
    cin >> W >> H;
    board.resize(H);
    visit.resize(H, vector<bool>(W, false));

    for (int i = 0; i < H; ++i)
        cin >> board[i];

    cin >> N;
    int x[N + 1], y[N + 1];
    x[0] = y[0] = 0;
    for (int i = 1; i <= N; ++i)
        cin >> x[i] >> y[i];

    bool not_found = true;
    visit[0][0] = true;

    for (int t = 0; t <= N; ++t) {
        if (Search(x[t], y[t])) {
            cout << t << endl;
            not_found = false;
            break;
        }
    }

    if (not_found)
        cout << "-1\n";

    return 0;
}