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 <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit
#include <cstdio>	// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>	// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define DEBUG 0

using namespace std;

const int dir[][2] = { {-1, 0 }, { 0, 1 }, {1, 0 }, {0, -1 } };

char f[1000][1000];
//bool used[1000][1000];
int par[1000*1000];
int w, h;


// ØÌªðßé
int root (int x )
{
	return (par[x] == x ? x : par[x] = root (par[x] ) );
}

// xÆyÌ®·éWð}[W
void unite (int x, int y )
{
	x = root (x);
	y = root (y);
	if (x != y ){ 
		(y < x ? par[x] = y : par[y] = x ) ;
	} // end if
}

// xÆyª¯¶WÉ®·é©Û©
bool same (int x, int y )
{
	return (root (x) == root (y) );
}


void dfs (int row, int col )
{
//	used[row][col] = true;
	rep (k, 4 ){
		int nr = row + dir[k][0];
		int nc = col + dir[k][1];
		if (nr < 0 || nc < 0 || nr >= h || nc >= w || f[nr][nc] == '#' ) continue;
		unite (row*w + col, nr*w + nc  );
//		if (!used[nr][nc] )
//			dfs (nr, nc );
	} // end rep
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.luckydip2", "r", stdin );

//	memset (used, false, sizeof (used ) );

	scanf (" %d %d", &w, &h );
	int g = 0;		// Üª éÊu
	rep (i, h*w ){
		scanf (" %c", f[i/w]+(i%w) );
		if (f[i/w][i%w] == 't' ){
			g = i;
		} // end if
		par[i] = i;
	} // end rep
	rep (i, h ) rep (j, w ) if (f[i][j] != '#' ) dfs (i, j );

	if (same (0, g ) ){
		printf ("0\n" );
		return 0;
	} // end if	

	int n;	// ðú³êéÇÌ
	scanf (" %d", &n );
	for (int i = 1; i <= n; i++ ){
		int x, y;
		scanf (" %d %d", &x, &y );
		f[y][x] = '.';
		dfs (y, x );
		if (same (0, g ) ){
			printf ("%d\n", i );
			return 0;
		} // end if
	} // end rep

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