uva 10047优先队列+BFS

题目大意：

有一个独轮车，轮子上有5个不同的扇形颜色区域， 每个区域大小都是相等的（72°扇形）。 骑着这个车子在一个广场上行走。

广场是有大小相同的正方形瓷砖铺成的。 独轮车从一块瓷砖走向相邻的一块，轮子正好转72°。只能走向相邻的上、下、左、右的瓷砖。从一个瓷砖走向下一个瓷砖耗费1秒钟。车子转方向90°耗费1秒钟，连转180°就要费2秒钟。白色的瓷砖可以走，黑色的不可以走（黑色的用"#“代替，白色的用”."代替）。

题目要求从标有S的地方走向标有T的地方。轮子在开始时，蓝色是贴着地面的，要求到达终点时，也正好是蓝色贴着地面的。

如果可以到达的话，输出所需要的最短时间。否则输出 destination not reachable。

思路：

需要用到优先队列，只是BFS不能得到答案。

代码

#include <bits/stdc++.h>
using namespace std;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int M,N,start_x,start_y,end_x,end_y,step;
char mapp[30][30];
bool vis[30][30][4][5];
struct Node
{
    int x,y;
    int color;
    int time;
    int dir;
    friend bool operator < (const Node &a,const Node &b){
        return a.time> b.time;
    }
};

Node beginn,q,t;
priority_queue<Node> que;
void bfs()
{
    while(!que.empty()) que.pop();
    que.push(beginn);
    vis[beginn.x][beginn.y][beginn.dir][beginn.color] = true;
    while(!que.empty()){
        q = que.top();
        que.pop();
        for(int i=0;i<4;i++)
        {
            int dx=q.x+dir[i][0];
            int dy=q.y+dir[i][1];
            if(dx>=0&&dx<M&&dy>=0&&dy<N&&mapp[dx][dy]!='#'){
                if(q.dir==i){
                    t.time=q.time+1;
                    t.dir=i;
                    t.x=q.x,t.y=q.y;
                    t.color=(q.color+1)%5;
                }
                else {
                    if(abs(q.dir-i)==2)
                        t.time=q.time+2;
                    else
                        t.time =q.time+1;
                    t.dir=i; t.x=q.x; t.y=t.y;
                    t.color=q.color;
                }
                if(!vis[t.x][t.y][i][t.color]){
                    if(t.x==end_x && t.y==end_y && t.color==0){
                        printf("minimum time = %d sec\n", t.time);
                        return;
                    }
                    que.push(t);
                    vis[t.x][t.y][i][t.color]=true;
                }

            }
        }
    }
    printf("destination not reachable\n");
}

int main()
{
    int cas=1;
    while(~scanf("%d %d%*c", &M, &N) && M && N)
    {
        bool is_findS=false,is_findT=false;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<M;i++)
        {
            gets(mapp[i]);
            if(!is_findS||!is_findT)
            {
                for(int k=0;k<strlen(mapp[i]);k++){
                    if(mapp[i][k]=='S'){
                        start_x=i,start_y=k,is_findS=true;
                    }
                    if(mapp[i][k]=='T'){
                        end_x=i,end_y=k,is_findT=true;
                    }
                }
            }
        }
        beginn.x=start_x,beginn.y=start_y,beginn.color=0,beginn.time=0;
        beginn.dir=0;
        if(cas!=1) cout<<endl;
        printf("Case #%d\n", cas++);
        bfs();
    }
}