UVA10047_The Monocycle

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

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

问某人从一个点走向另一个点的最短时间，并且走过的路程是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,color

char 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;

}