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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(){
		row = col = 0;
	}
	Info(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};

int N,W,H;
int* boss,*height;
bool* check;
char** map;

int translate(int row,int col){
	return row*W+col;
}

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

int is_Same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	if(boss_x == boss_y)return;

	if(height[x] > height[y]){

		boss[boss_y] = boss_x;

	}else if(height[x] < height[y]){

		boss[boss_x] = boss_y;

	}else{ //height[x] == height[y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

int main(){

	scanf("%d %d",&W,&H);

	int limit = W*H;

	boss = new int[limit];
	height = new int[limit];
	check = new bool[limit];

	for(int i = 0; i < limit; i++){
		boss[i] = i;
		height[i] = 0;
		check[i] = false;
	}

	int dip;

	map = new char*[H];
	for(int i = 0; i < H; i++)map[i] = new char[W+1];

	for(int row = 0; row < H; row++){
		scanf("%s",map[row]);
		for(int col = 0; col < W; col++){
			if(map[row][col] == 't'){
				dip = translate(row,col);
			}
		}
	}

	int tmp,next_row,next_col,next;
	queue<Info> Q;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			if(map[row][col] != '#' && check[tmp=translate(row,col)] == false){
				check[tmp] = true;

				Q.push(Info(row,col));

				while(!Q.empty()){

					tmp = translate(Q.front().row,Q.front().col);

					for(int i = 0; i < 4; i++){
						next_row = Q.front().row + diff_row[i];
						next_col = Q.front().col + diff_col[i];
						next=translate(next_row,next_col);

						if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && check[next] == false){
							unite(tmp,next);
							check[next] = true;
							Q.push(Info(next_row,next_col));
						}
					}
					Q.pop();
				}

			}
		}
	}

	if(is_Same(0,dip)){
		printf("0\n");
		return 0;
	}

	int N;
	scanf("%d",&N);

	int tmp_col,tmp_row;

	for(int loop = 1; loop <= N; loop++){
		scanf("%d %d",&tmp_col,&tmp_row);

		if(map[tmp_row][tmp_col] == '#'){
			map[tmp_row][tmp_col] = '.';

			if(rangeCheck(tmp_row-1,tmp_col) == true && map[tmp_row-1][tmp_col] != '#'){
				unite(translate(tmp_row-1,tmp_col),translate(tmp_row,tmp_col));
			}
			if(rangeCheck(tmp_row+1,tmp_col) == true && map[tmp_row+1][tmp_col] != '#'){
				unite(translate(tmp_row,tmp_col),translate(tmp_row+1,tmp_col));
				if(rangeCheck(tmp_row-1,tmp_col) == true){
					unite(translate(tmp_row-1,tmp_col),translate(tmp_row+1,tmp_col));
				}
			}

			if(rangeCheck(tmp_row,tmp_col-1) == true && map[tmp_row][tmp_col-1] != '#'){
				unite(translate(tmp_row,tmp_col-1),translate(tmp_row,tmp_col));
			}
			if(rangeCheck(tmp_row,tmp_col+1) == true && map[tmp_row][tmp_col+1] != '#'){
				unite(translate(tmp_row,tmp_col),translate(tmp_row,tmp_col+1));
				if(rangeCheck(tmp_row,tmp_col-1) == true){
					unite(translate(tmp_row,tmp_col-1),translate(tmp_row,tmp_col+1));
				}
			}

			if(is_Same(0,dip)){
				printf("%d\n",loop);
				return 0;
			}
		}
	}

	printf("-1\n");
	return 0;
}