首页 > 代码库 > UVA10047_The Monocycle

UVA10047_The Monocycle

2024-07-12 00:16:36   215人阅读

这题。。。。有点奇葩，但是不难。

在矩形方阵里，某人可以往前走或者左拐右拐。都需要消耗一个单位时间。

问某人从一个点走向另一个点的最短时间，并且走过的路程是5的倍数。

由于n，m都小，直接f[n][m][direction][color]，表示所有状态，bfs更新即可。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std;int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1};int f[30][30][4][5];//position,direction,colorchar s[30][30];int n,m;bool inside(int cx,int cy){    return cx>0 && cx<=n && cy>0 && cy<=m;}void _init(){    for (int i=1; i<=n; i++)        for (int j=1; j<=m; j++)            for (int x=0; x<4; x++)                for (int y=0; y<5; y++)                    f[i][j][x][y]=99999999;}int _process(){    queue<int> qx,qy,qd,qc;    for (int i=1; i<=n; i++)    {        scanf("%s",s[i]+1);        for (int j=1; s[i][j]; j++)            if (s[i][j]==‘S‘)            {                f[i][j][0][0]=0;                qx.push(i),qy.push(j),qd.push(0),qc.push(0);            }    }    while (!qx.empty())    {        int cx=qx.front(),cy=qy.front(),cd=qd.front(),cc=qc.front();        qx.pop(),qy.pop(),qd.pop(),qc.pop();        int tmp=(cd+3)%4;        if (f[cx][cy][cd][cc]+1<f[cx][cy][tmp][cc])        {            f[cx][cy][tmp][cc]=f[cx][cy][cd][cc]+1;            qx.push(cx),qy.push(cy),qd.push(tmp),qc.push(cc);            /*            cout<<" inside : "<<cx<<‘ ‘<<cy<<‘ ‘<<tmp<<‘ ‘;            cout<<cc<<‘ ‘<<f[cx][cy][tmp][cc]<<endl;            */        }        tmp=(cd+1)%4;        if (f[cx][cy][cd][cc]+1<f[cx][cy][tmp][cc])        {            f[cx][cy][tmp][cc]=f[cx][cy][cd][cc]+1;            qx.push(cx),qy.push(cy),qd.push(tmp),qc.push(cc);            /*            cout<<" inside : "<<cx<<‘ ‘<<cy<<‘ ‘<<tmp;            cout<<‘ ‘<<cc<<‘ ‘<<f[cx][cy][tmp][cc]<<endl;            */        }        if (!inside(cx+dx[cd],cy+dy[cd]) || s[cx+dx[cd]][cy+dy[cd]]==‘#‘) continue;        if (f[cx][cy][cd][cc]+1<f[cx+dx[cd]][cy+dy[cd]][cd][(cc+1)%5])        {            f[cx+dx[cd]][cy+dy[cd]][cd][(cc+1)%5]=f[cx][cy][cd][cc]+1;            if (s[cx+dx[cd]][cy+dy[cd]]==‘T‘ && (cc+1)%5==0) return f[cx+dx[cd]][cy+dy[cd]][cd][0];            qx.push(cx+dx[cd]),qy.push(cy+dy[cd]),qd.push(cd),qc.push((cc+1)%5);            /*            cout<<" inside : "<<cx+dx[cd]<<‘ ‘<<cy+dy[cd]<<‘ ‘<<cd;            cout<<‘ ‘<<(cc+1)%5<<‘ ‘<<f[cx+dx[cd]][cy+dy[cd]][cd][(cc+1)%5]<<endl;            */        }    }    return -1;}int main(){    //freopen("data.in","rb",stdin);    int cas=0;    while (scanf("%d%d",&n,&m) && (n|m))    {        _init();        int ans=_process();        if (cas) printf("\n");        printf("Case #%d\n",++cas);        if (ans==-1) puts("destination not reachable");            else printf("minimum time = %d sec\n",ans);    }    return 0;}

　　


联系
我们