预言家 大A 和 大B 在玩抓人游戏，大A每一个时间单位均移动一个单位，如果 大A 在某个单位时间与 大B 站在一起，那么 大A 就获胜，若T个时间单位后，大A 没获胜则 大B 获胜。但是 大A 是预言家，因此他能够预判 大B 的行动轨迹。

题目描述 大B 在一个边长为 $N$ 的正方形迷宫内。大A 想让你帮他算算，他最短可以在几个单位时间后获胜。

大A 把这个房间的地图用符号画了出来，他规定:

$.$ 代表这个地方是没有障碍的。

$*$ 代表这个地方有障碍物，是不可走的。

$A$ 代表大A的初始位置。

$B$ 代表大B的初始位置。

输入格式 第一行 $2$ 个整数，$N$ 和 $T$ ，空格隔开。

接下来的 $N$ 行，每行 $N4 个字符，表示 大A 画的地图。

接下来的 $T$ 行，每行 $2$ 个整数$x$和$y$，表示 大B 在每个时间单位时的位置。

输出格式 第一行一个整数 $K$ ，表示 大A 最短可以在过了 $K$ 个单位时间后 获胜，如果他不可以在 大B 胜利前获胜，那么请输出 $-1$。

输入输出样例 输入 #1

5 3
.  *  *  *  *
*  .  .  B  .
A  .  *  *  *
*  *  *  *  *
.  .  .  .  .
2 3
2 2

输出 #1

2

说明/提示

样例解释#1：

大A 移动路径：

3 1 -> 3 2 -> 2 2

大B 移动路径：

2 4 -> 2 3 -> 2 2，

因此最短时间为

2

。

提示：为了游戏的可玩性，所以他们规定 大A 走过的路不可再走。

对于所有数据

$5 ≤ N ≤ 100 , 1 ≤ T ≤ 1000$

#include <bits/stdc++.h>
using namespace std;
char a[1005][1005];
int b1[1005],b2[1005],b[1005][1005],fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool v[1005][1005];
int n,ax,t,ay,bx,e,by,s;
queue<int>qx,qy;
void f(){
	int j;
	qx.push(ax);
	qy.push(ay);
	a[ax][ay]=0;
	v[ax][ay]=true;
	while(!qx.empty()){
		int x=qx.front(),y=qy.front();
		qx.pop();
		qy.pop();
		if(j<=t){
			bx=b1[j];
			by=b2[j];
		}
		for(int i=0;i<4;i++){
            e=0;
			int nx=x+fx[i][0];
			int ny=y+fx[i][1];
			if(nx>0&&ny>0&&nx<=n&&ny<=n&&a[nx][ny]!='*'&&!v[nx][ny]){
				v[nx][ny]=true;
				b[nx][ny]=b[x][y]+1;
				qx.push(nx);
				qy.push(ny);
			}
		}
	}
	cout<<b[bx][by];
	return;
}
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			if(a[i][j]=='A'){
				ax=i;
				ay=j;
			}else if(a[i][j]=='B'){
				bx=i;
				by=j;
			}
		}
	}
	for(int i=1;i<=t;i++){
		cin>>b1[i]>>b2[i];
	}
	f();	
	return 0;
}