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<queue>

using namespace std;

typedef pair<int,int> P;

const int MAX = 1001;
char field[MAX][MAX];
bool come[MAX][MAX];
vector<P> V;
int W,H,gh,gw;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void print(){
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++) cout << come[i][j];
    cout << endl;
  }
  cout << endl;
}
void input(){
  cin >> W >> H;

  for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++){
      cin >> field[i][j];
      if(field[i][j] == 't'){
	gh = i;
	gw = j;
      }
    }

  int N;
  cin >> N;
  V.resize(N);
  for(int i = 0; i < N; i++) cin >> V[i].first >> V[i].second;
}

bool isInside(int x, int y){return 0<=x&&x<W&&0<=y&&y<H;}
/*
void dfs(int row, int col){
  //  cout << row << " " << col << endl;
  if(come[row][col]) return;
  come[row][col] = true;

  for(int i = 0; i < 4; i++){
    int nr = row+dy[i];
    int nc = col+dx[i];
    if(!isInside(nc,nr)) continue;
    if(field[nr][nc] == '#') continue;
    dfs(nr,nc);
  }
}
*/
void bfs(int row, int col){
  queue<P> Q;
  Q.push(P(row,col));

  while(!Q.empty()){
    P p = Q.front(); Q.pop();
    if(come[p.first][p.second]) continue;
    come[p.first][p.second] = true;

    for(int i = 0; i < 4; i++){
      P nex;
      nex.first = p.first + dy[i];
      nex.second = p.second + dx[i];
      if(!isInside(nex.second,nex.first)) continue;
      if(field[nex.first][nex.second] == '#') continue;
      Q.push(nex);
    }
  }
}

int solve(){
  bfs(0,0);
  if(come[gh][gw]) return 0;

  //  print();

  for(int i = 0; i < (int)V.size(); i++){
    bool reach = false;
    field[V[i].second][V[i].first] = '.';
    for(int j = 0; j < 4; j++){
      int pr = V[i].second-dy[j];
      int pc = V[i].first-dx[j];
      
      if(!isInside(pc,pr)) continue;
      
      reach = reach||come[pr][pc];
    }
    if(reach) bfs(V[i].second,V[i].first);
    if(come[gh][gw]) return i+1;

    //   print();
  }
  return -1;
}

int main(){
  input();
  cout << solve() << endl;
  return 0;
}