uva10067 Playing with Wheels 【建图+最短路】

水深无声 2022-08-12 00:07 103阅读 0赞

题目：[uva10067 Playing with Wheels ][uva10067 Playing with Wheels]

题意：给出一个机器，有四个循环的轮子，见图，然后给出一个初始数和目标数，然后期间不能出现的数字，每一分钟可以拨动一个数，问你最短需要的时间。

![p10067.gif][]

分析：这个题目可以转化为求图的最短路。

因为有对于一个当前状态，有8种可以转化为的状态，那么我们可以把每一种状态转化为一个点，然后状态之间连长度 1 的边，然后求一次初始状态到目标状态的最短路。

开始的时候我们每一组数据建图一次，下来0.9s，然后优化了一下，就是在每次建图不能到达的边删除之后求完之后恢复过来，这样不用每次建图，下来0.19s，时间相当快了。就只是一个spfa的时间复杂度O（m）、

AC代码：

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <utility>
    #include <cmath>
    using namespace std;
    const int N = 10005;
    const int M = 10000;
    const int inf = 0x3f3f3f3f;
    struct Node
    {
        int x,len;
    };
    vector<Node> v[N];
    void add_Node(int x,int y,int len)
    {
        v[x].push_back((Node){y,len});
        v[y].push_back((Node){x,len});
    }
    int count(int i,int j,int k,int f)
    {
        return ((i+10)%10)*1000+((j+10)%10)*100+((k+10)%10)*10+(f+10)%10;
    }
    int dir[10][5]=
    {
        {0,0,0,1},{0,0,0,-1},
        {0,0,1,0},{0,0,-1,0},
        {0,1,0,0},{0,-1,0,0},
        {1,0,0,0},{-1,0,0,0}
    };
    void build(int i,int j,int k,int f)
    {
        int tmp=count(i,j,k,f);
        for(int p=0; p<8; p++)
        {
            int tmp1=count(i+dir[p][0],j+dir[p][1],k+dir[p][2],f+dir[p][3]);
            add_Node(tmp,tmp1,1);
        }
    }
    void isit()
    {
        for(int i=0; i<10; i++)
            for(int j=0; j<10; j++)
                for(int k=0; k<10; k++)
                    for(int f=0; f<10; f++)
                        build(i,j,k,f);
    }
    int dis[N];
    void spfa(int s)  
    {
        int i;
        queue<int> q;
        for(i=0; i<N; i++)
            dis[i]=inf;
        dis[s]=0;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(i=0; i<v[u].size(); i++)
            {
                Node p=v[u][i];
                if(dis[p.x]>dis[u]+p.len)
                {
                    dis[p.x]=dis[u]+p.len;
                    q.push(p.x);
                }
            }
        }
    }
    int dx[N],dy[N],dz[N],dk[N];
    int main()
    {
        int T;
        isit();
        scanf("%d",&T);
        while(T--)
        {
            int x,y,z,k;
            scanf("%d%d%d%d",&x,&y,&z,&k);
            int st=x*1000+y*100+z*10+k;
            scanf("%d%d%d%d",&x,&y,&z,&k);
            int en=x*1000+y*100+z*10+k;
            int cc;
            scanf("%d",&cc);
            for(int i=0;i<cc;i++)
            {
                scanf("%d%d%d%d",&dx[i],&dy[i],&dz[i],&dk[i]);
                int tmp=count(dx[i],dy[i],dz[i],dk[i]);
                v[tmp].clear();
            }
            spfa(st);
            if(dis[en]>=inf)
                puts("-1");
            else
                printf("%d\n",dis[en]);
            for(int i=0;i<cc;i++)
            {
                build(dx[i],dy[i],dz[i],dk[i]);
            }
        }
    }

[uva10067 Playing with Wheels]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1008
[p10067.gif]: /images/20220810/7f06ac983b884859a14cc49d7de790c1.png