一家科技公司有一块试验地用于测试自动驾驶系统。试验地由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

13 4 5? 2 2* 1 2? 2 2* 2 1? 2 2

Sample Output

22-1

Author

Claris

Source

"字节跳动杯"杭州电子科技大学第十九届程序设计竞赛

 

 

这是一个图比较小 但是询问次数非常多的普通bfs  比赛的时候没有想出来很可惜  

#include
       
        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+5int dx[4]={
     0,1,0,-1};int dy[4]={
     1,0,-1,0};int n,m,ex,ey;int d[N][N];int mp[N][N];struct node{    int x,y;};void bfs(){    CLR(d,-1);    d[1][1]=0;    node u,v;    u.x=1;    u.y=1;    queue
        
         q;    q.push(u);    while(!q.empty())    {        u=q.front();q.pop();        rep(i,0,3)        {            node v=u;            v.x+=dx[i];            v.y+=dy[i];            if(d[v.x][v.y]!=-1)continue;            if(mp[v.x][v.y]==1)continue;            if(  !(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m)  )continue;            d[v.x][v.y]=d[u.x][u.y]+1;            q.push(v);        }    }}int main(){   int cas;   RI(cas);   while(cas--)   {       CLR(mp,0);       int q;       RIII(n,m,q);       bfs();       while(q--)       {           char s[4];           RS(s);           RII(ex,ey);           if(s[0]=='*')           {               mp[ex][ey]=1;               bfs();           }           else printf("%d\n",d[ex][ey]);       }   }    return 0;}