Problem A: The Monocycle

uva10047：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=988

题意：题目意思比较绕，就是给出图，从起点'S'出发，到终点'T'，有这样的车轮：车轮每转90度，时间加1，上面的均匀5个扇形，从起点开始，是blue色扇形着地，方向向‘上’，然后求出从起点到终点的最后终点是blue扇形着地的最小时间。

题解：用BFS，counts【x】【y】【dir】【co】表示到达x，y时候方向为dir，颜色是co的最小步数，然后就可以BFS。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define INF 1000000000

 using namespace std;

 const int N=;

 struct Node{

    int x;

    int y;

    int step;

    int dir;

    int color;

 };

 int n,m;

 char map[N][N];

 int counts[N][N][N][N];

 int sx,sy;

 int ex,ey;

 void BFS(int x,int y,int d,int color){//0是北1是西2是南3是东  0是绿色，1是白2蓝3红4黑

     queue<Node>Q;

     Node temp;

     temp.x=x;

     temp.y=y;

     temp.dir=d;

     temp.color=color;

     temp.step=;

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

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

            for(int k=;k<=;k++)

                for(int g=;g<=;g++)

                  counts[i][j][k][g]=INF;

      Q.push(temp);

     counts[x][y][d][color]=;

     int dir[][]={{-,},{,-},{,},{,}};

     while(!Q.empty()){

         Node tt=Q.front();

         Q.pop();

         int xx=tt.x;

         int yy=tt.y;

         int step=tt.step;

         int dd=tt.dir;

         int co=tt.color;

         if(step+<counts[xx][yy][(dd+)%][co]){

             counts[xx][yy][(dd+)%][co]=step+;

             Node tmp;

             tmp.x=xx;

             tmp.y=yy;

             tmp.dir=(dd+)%;

             tmp.step=step+;

             tmp.color=co;

             Q.push(tmp);

         }

         if(step+<counts[xx][yy][(dd+)%][co]){

             counts[xx][yy][(dd+)%][co]=step+;

             Node tmp;

             tmp.x=xx;

             tmp.y=yy;

             tmp.dir=(dd+)%;

             tmp.step=step+;

             tmp.color=co;

             Q.push(tmp);

         }

            int xxx=xx+dir[dd][];

            int yyy=yy+dir[dd][];

            if(xxx>=&&xxx<=n&&yyy>=&&yyy<=m){

                 if(map[xxx][yyy]!='#'){

                     if(step+<counts[xxx][yyy][dd][(co+)%]){

                         counts[xxx][yyy][dd][(co+)%]=step+;

                         Node tmp;

                         tmp.x=xxx;

                         tmp.y=yyy;

                         tmp.step=step+;

                         tmp.color=(co+)%;

                         tmp.dir=dd;

                         Q.push(tmp);

                     }

                 }

            }

         }

 }

 int main(){

     int tt=;

    while(~scanf("%d%d",&n,&m)&&n>){

         if(tt!=)printf("\n");

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

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

           cin>>map[i][j];

           if(map[i][j]=='S'){

             sx=i;

             sy=j;

           }

           if(map[i][j]=='T'){

             ex=i;

             ey=j;

           }

        }

       BFS(sx,sy,,);

       int minn=INF;

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

       for(int i=;i<=;i++){

         minn=min(minn,counts[ex][ey][i][]);

       }

       if(minn==INF)printf("destination not reachable\n");

       else

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

    }

 }

巴特西

Problem A: The Monocycle

最新文章

热门文章