自动驾驶系统 bfs

2024-04-11 23:03:01

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

Sample Output

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 ;

}

码农公寓