UVA 1600 Patrol Robot

深藏阁楼爱情的钟 2021-12-07 14:11 154阅读 0赞

题目链接

[https://vjudge.net/problem/UVA-1600][https_vjudge.net_problem_UVA-1600]

典型的bfs模拟题，但我实在是菜。

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define P pair<int,int>
    int dx[5]={-1,0,0,1};
    int dy[5]={
        0,-1,1,0};
    int d[25][25];
    int a[25][25];
    int vis[25][25][25];
    int n,m,k;
    struct Point{
        int x;int y;
    };
    struct Stat{
        Point pos;
        int turbo;
    };
    int  bfs(int x1,int y1,int x2,int y2)
    {
        Stat s;
        memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));
        queue<Stat>que;
        s.pos.x=x1;
        s.pos.y=y1;
        if(a[x1][y1]==1)
        s.turbo=1;
        else
        s.turbo=0;
        if(s.turbo==1&&k==0)
        return -1;
        que.push(s);
        int ex,ey,size;
        while(que.size()>0)
        {
            Stat s1;
            s1=que.front();
            ex=s1.pos.x;
            ey=s1.pos.y;
            size=s1.turbo;
            que.pop();
            if(ex==x2&&ey==y2)
            {
                return d[ex][ey];
            }
            for(int i=0;i<4;i++)
            {
                int nx=ex+dx[i];
                int ny=ey+dy[i];
                Stat s2;
                s2.pos.x=nx;s2.pos.y=ny;
                if(size<=k)
                    {
                        if(a[nx][ny]==0)
                        {
                            s2.turbo=0;
                        }
                        else
                        {
                            s2.turbo=size+1;
                        }
                    }
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny][s2.turbo]==0)
                {
                    if(s2.turbo<=k)
                    {
                        que.push(s2);
                        vis[nx][ny][s2.turbo]=1;
                        d[nx][ny]=d[ex][ey]+1;        
                    }        
                }
            }
         }
         return -1; 
    }
    int main()
    { 
        int T,ans;
        cin>>T;
        while(T--)
        {
            cin>>n>>m>>k;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    cin>>a[i][j];
                }
            }
            ans=bfs(1,1,n,m);
            cout<<ans<<"\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hh13579/p/11188257.html

[https_vjudge.net_problem_UVA-1600]: https://vjudge.net/problem/UVA-1600