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 <iostream>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int INF = 1e+9;
typedef pair<int,int> P;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int w, h, n;
string m[1001];
int ans = -1;
bool ans_flag = false;

// open[y][x] : (x,y)ªJ­ÔÍopen[y][x]AJ©È¢Æ«Í-1
int open[1001][1001] = {0};
// is_door[i] : iÔãÉJ­hAªX^[g©çBÂ\©Ç¤©
bool is_door[1001];
// vp[i] : iÔãÉJ­hAÌÀW
vector<P> vp(1001);

void debug(){
	for(int y=0 ; y < h ; y++ ){
		cout << m[y] << endl;
	}
	cout << endl;
}

void solve(){	
	is_door[0] = true;
	vp[0].first = 0;
	vp[0].second = 0;
	for(int i=0 ; i <= n && ans_flag == false ; i++ ){
		m[vp[i].second][vp[i].first] = '.';
		if( is_door[i] == false ) continue;
		
		stack<P> st;
		int sx = vp[i].first;
		int sy = vp[i].second;
		P sp(sx,sy);
		st.push( sp );
		while( !st.empty() && ans_flag == false ){
			P p = st.top(); st.pop();
			int x = p.first;
			int y = p.second;
			
			for(int j=0 ; j < 4 && ans_flag == false ; j++ ){
				int mx = x + dx[j];
				int my = y + dy[j];
				if( mx < 0 || my < 0 || mx >= w || my >= h ) continue;
				
				if( m[my][mx] == 't' ){
					ans = i;
					ans_flag = true;
				}
				if( open[my][mx] != -1 ){
					is_door[open[my][mx]] = true;
				}
				if( m[my][mx] == '.' ){
					P p(mx,my);
					st.push( p );
					m[my][mx] = '*';
				}
			}
		}
	}
}

int main(){
	// ú»
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			open[y][x] = -1;
		}
	}
	for(int i=0 ; i < n ; i++ ){
		is_door[i] = false;
	}
	
	cin >> w >> h;
	for(int y=0 ; y < h ; y++ ){
		cin >> m[y];
	}
	cin >> n;
	for(int i=0 ; i < n ; i++ ){
		int x, y;
		cin >> x >> y;
		open[y][x] = i+1;
		P p(x,y);
		vp[i+1] = p; 
	}
	if( m[0][0] == 't' ){
		cout << 0 << endl;
	}else{
		solve();
		//debug();
		cout << ans << endl;
	}
}