一家科技公司有一块试验地用于测试自动驾驶系统。试验地由n×m个格子组成，从上到下依次编号为第1到n行，从左到右依次编号为第1到m列。试验车位于其中的某个格子上，每次自动驾驶系统可以控制汽车往上下左右移动一格。汽车不能走出边界，也不能碰到障碍格。
你需要编写自动驾驶系统中的导航部分。在测试的一开始，试验地里没有任何障碍。你的程序会依次收到q条信息，它们的格式是以下两种之一：
? x y，表示询问从第1行第1列的格子出发，到达第x行第y列的格子最少需要移动多少次。
* x y，表示第x行第y列的格子变成了障碍格。
Input
第一行包含一个正整数T(1≤T≤5)，表示测试数据的组数。
每组数据第一行包含三个正整数n,m,q(1≤n,m≤50,1≤q≤100000)，表示试验地的尺寸以及信息的数量。
接下来m行，每行描述一条信息。其中1≤x,y≤n，保证每个格子不会被重复变成障碍格多次，且(1,1)不会变成障碍格。
Output
对于每个询问输出一行一个整数，即最少移动次数，若无法到达请输出−1。
Sample Input
1
3 4 5
? 2 2
* 1 2
? 2 2
* 2 1
? 2 2
Sample Output
2
2
-1
Author
Claris
Source
"字节跳动杯"杭州电子科技大学第十九届程序设计竞赛
这是一个图比较小 但是询问次数非常多的普通bfs 比赛的时候没有想出来很可惜
#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define inf 0x3f3f3f3f
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 500+5
int dx[]={,,,-};
int dy[]={,,-,};
int n,m,ex,ey;
int d[N][N];
int mp[N][N];
struct node
{
int x,y;
};
void bfs()
{
CLR(d,-);
d[][]=;
node u,v;
u.x=;
u.y=;
queue<node>q;
q.push(u);
while(!q.empty())
{
u=q.front();q.pop();
rep(i,,)
{
node v=u;
v.x+=dx[i];
v.y+=dy[i];
if(d[v.x][v.y]!=-)continue;
if(mp[v.x][v.y]==)continue;
if( !(v.x>=&&v.x<=n&&v.y>=&&v.y<=m) )continue;
d[v.x][v.y]=d[u.x][u.y]+;
q.push(v);
}
}
}
int main()
{
int cas;
RI(cas);
while(cas--)
{
CLR(mp,);
int q;
RIII(n,m,q);
bfs();
while(q--)
{
char s[];
RS(s); RII(ex,ey);
if(s[]=='*')
{
mp[ex][ey]=;
bfs();
}
else printf("%d\n",d[ex][ey]);
}
}
return ;
}