大白图论第二题···

题意：独轮车的*被均分成五块，每块一个颜色，每走过一个格子恰好转过一个颜色。

在一个迷宫中，只能向前走或者左转90度或右转90度（我曾天真的认为是向左走和向右走···），每个操作的时间是1s。

在起点*的绿色块着地，方向向北，要求到终点时同样是绿色块着地，方向不限，求最短时间，若走不到输出”destination not reachable“。每个样例中间空一行（没错我又因为这个wa了···uva上竟然没有pe···【捂脸跑开】）

解法：BFS。visit数组多加两维记录方向和颜色，dir数组从北开始按顺时针或逆时针存，当下标的奇偶性和当前方向不同时为向左右转，当到达终点并颜色为起始颜色时得到答案。

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<map>

#include<queue>

#define ll long long

using namespace std;

struct node

{

    int x,y,d,c,step;//横纵坐标，方向，颜色，时间

    node(int x,int y,int d,int c,int step):x(x),y(y),d(d),c(c),step(step) {}

    node() {}

};

int dir[4][2]= {-1,0,0,1,1,0,0,-1};//顺时针存，一维下标奇偶性相同的为相对的两个方向

int main()

{

    int cnt=1;

    int n,m;

    while(~scanf("%d%d",&n,&m)&&!(n==0&&m==0))

    {

        int stx,sty;

        string maze[30];

        for(int i=0; i<n; i++)

        {

            cin>>maze[i];

            for(int j=0; j<m; j++)

                if(maze[i][j]=='S')

                {

                    stx=i;

                    sty=j;//记录起始点

                }

        }

        int visit[30][30][4][5]= {0};//横纵坐标，方向，颜色

        queue<node> q;

        q.push(node(stx,sty,0,0,0));

        visit[stx][sty][0][0]=1;

        int ans=-1;

        while(!q.empty())

        {

            node temp=q.front();

            q.pop();

            if(maze[temp.x][temp.y]=='T'&&temp.c==0)

            {

                ans=temp.step;

                break;

            }

            for(int i=0; i<4; i++)

            {

                if(!((i!=temp.d)&&((i&1)==(temp.d&1))))//判断反向是否合法【看起来写屎了···

                {

                    int tx=temp.x+dir[i][0],ty=temp.y+dir[i][1];

                    if(i==temp.d)//直走的情况

                    {

                        if(tx>=0&&tx<n&&ty>=0&&ty<m&&maze[tx][ty]!='#'&&!visit[tx][ty][i][(temp.c+1)%5])

                        {

                            q.push(node(tx,ty,i,(temp.c+1)%5,temp.step+1));

                            visit[tx][ty][i][(temp.c+1)%5]=1;

                        }

                    }

                    else//转弯的情况

                    {

                        if(!visit[temp.x][temp.y][i][temp.c])

                        {

                            visit[temp.x][temp.y][i][temp.c]=1;

                            q.push(node(temp.x,temp.y,i,temp.c,temp.step+1));

                        }

                    }

                }

            }

        }

        if(cnt!=1)

            puts("");//【吐槽】再次被坑

        printf("Case #%d\n",cnt++);

        if(ans!=-1)

            printf("minimum time = %d sec\n",ans);

        else

            puts("destination not reachable");

    }

    return 0;

}

代码丑···见谅