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 <algorithm>
#include <bitset>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

template <int MAX_N>
class UnionFind {
public:
    int parent[MAX_N];
    int rank[MAX_N];

    UnionFind() {
    }

    void init(int n) {
        for (int j = 0; j < n; ++j) {
            parent[j] = j;
            rank[j] = 0;
        }
    }

    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;

        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
            if (rank[x] == rank[y]) {
                ++rank[x];
            }
        }

        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;

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

int W, H;
string s[1000];
int N;
int x[1010], y[1010];

UnionFind<1010*1010> uf;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> W >> H;
    for (int j = 0; j < H; ++j) {
        cin >> s[j];
    }
    cin >> N;
    for (int j = 0; j < N; ++j) {
        cin >> x[j] >> y[j];
    }

    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    uf.init(W*H);

    int start = 0;
    int goal;
    bool found = false;
    for (int j = 0; !found && j < H; ++j) {
        for (int k = 0; k < W; ++k) {
            if (s[j][k] == 't') {
                found = true;
                goal = j*W + k;
                break;
            }
        }
    }

    for (int j = 0; j < H; ++j) {
        for (int k = 0; k < W; ++k) {
            if (j < H-1) {
                if (s[j][k] != '#' && s[j+1][k] != '#') {
                    uf.unite(W*j+k, W*(j+1)+k);
                }
            }
            if (k < W-1) {
                if (s[j][k] != '#' && s[j][k+1] != '#') {
                    uf.unite(W*j+k, W*j+k+1);
                }
            }
        }
    }

    if (uf.same(start, goal)) {
        cout << 0 << endl;
        return 0;
    }

    for (int j = 0; j < N; ++j) {
        s[y[j]][x[j]] = '.';

        for (int k = 0; k < 4; ++k) {
            int ny = y[j] + dy[k];
            int nx = x[j] + dx[k];
            if (0 <= ny && ny < H && 0 <= nx && nx < W && s[ny][nx] != '#') {
                uf.unite(y[j]*W+x[j], ny*W+nx);
            }
        }

        if (uf.same(start, goal)) {
            cout << j+1 << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}