程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ3865:Superbot(BFS)

ZOJ3865:Superbot(BFS)

編輯:C++入門知識

ZOJ3865:Superbot(BFS)


Superbot is an interesting game which you need to control the robot on an N*M grid map.

\

As you see, it's just a simple game: there is a control panel with four direction left (1st position), right (2nd), up (3rd) and down (4th). For each second, you can do exact one of the following operations:

  • Move the cursor to left or right for one position. If the cursor is on the 1st position and moves to left, it will move to 4th position; vice versa.Press the button. It will make the robot move in the specific direction.Drink a cup of hot coffee and relax. (Do nothing)

    However, it's too easy to play. So there is a little trick: Every P seconds the panel will rotate its buttons right. More specifically, the 1st position moves to the 2nd position; the 2nd moves to 3rd; 3rd moves to 4th and 4th moves to 1st. The rotating starts at the beginning of the second.

    Please calculate the minimum time that the robot can get the diamond on the map.

    At the beginning, the buttons on the panel are "left", "right", "up", "down" respectively from left to right as the picture above, and the cursor is pointing to "left".

    Input

    There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

    The first line contains three integers N, M (2 <= N, M <= 10) and P (1 <= P <= 50), which represent the height of the map, the width of the map and the period that the panel changes, respectively.

    The following lines of input contains N lines with M chars for each line. In the map, "." means the empty cell, "*" means the trap which the robot cannot get in, "@" means the initial position of the robot and "$" means the diamond. There is exact one robot and one diamond on the map.

    Output

    For each test case, output minimum time that the robot can get the diamond. Output "YouBadbad" (without quotes) if it's impossible to get the diamond.

    Sample Input

    4
    3 4 50
    @...
    ***.
    $...
    5 5 2
    .....
    ..@..
    .*...
    $.*..
    .....
    2 3 1
    *.@
    $.*
    5 5 2
    *****
    ..@..
    *****
    $....
    .....
    

    Sample Output

    12
    4
    4
    YouBadbad

    Hint

    For the first example:
    0s: start
    1s: cursor move right (cursor is at "right")
    2s: press button (robot move right)
    3s: press button (robot move right)
    4s: press button (robot move right)
    5s: cursor move right (cursor is at "up")
    6s: cursor move right (cursor is at "down")
    7s: press button (robot move down)
    8s: press button (robot move down)
    9s: cursor move right (cursor is at "left")
    10s: press button (robot move left)
    11s: press button (robot move left)
    12s: press button (robot move left)

    For the second example:
    0s: start
    1s: press button (robot move left)
    2s: press button (robot move left)
    --- panel rotated ---
    3s: press button (robot move down, without changing cursor)
    4s: press button (robot move down)

    For the third example:
    0s: start
    1s: press button (robot move left)
    --- panel rotated ---
    2s: press button (robot move down)
    --- panel rotated ---
    3s: cursor move left (cursor is at "right")
    --- panel rotated ---
    4s: press button (robot move left)

     

    對於一個迷宮,@是起點,$是終點,.是路,*是陷阱不能走

    有四個控制鍵,從左到右是左右上下,但是這些控制鍵每P秒向右移動一個單位

    光標一開始在最左邊,光標每向左或者向右移動一個單位花費一秒,每按下一次花費一秒,機器人只有在按下按鈕的時候才會移動一次,求最少離開迷宮的時間

     

     

    #include 
    #include 
    #include 
    #include 
    #include 
    #include
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    #define ls 2*i
    #define rs 2*i+1
    #define up(i,x,y) for(i=x;i<=y;i++)
    #define down(i,x,y) for(i=x;i>=y;i--)
    #define mem(a,x) memset(a,x,sizeof(a))
    #define w(a) while(a)
    #define LL long long
    const double pi = acos(-1.0);
    #define Len 100005
    #define mod 1000000007
    const int inf = 1<<30;
    struct Point
    {
        int x,y,di,t;//di為光標停留的時間
        Point() {}
        Point(int a,int b,int c,int d):x(a),y(b),di(c),t(d) {}
    };
    
    int n,m,p;
    int di[4][2]= {{0,-1},{0,1},{-1,0},{1,0}};
    int dis[15][15][5];
    char mat[15][15];
    
    int main()
    {
        int t,i,j,k;
        scanf("%d",&t);
        w(t--)
        {
            scanf("%d%d%d",&n,&m,&p);
            int stx,sty,enx,eny;
            up(i,0,n-1)
            {
                scanf("%s",mat[i]);
                up(j,0,m-1)
                {
                    if(mat[i][j]=='@')
                    {
                        stx=i;
                        sty=j;
                    }
                    else if(mat[i][j]=='$')
                    {
                        enx=i;
                        eny=j;
                    }
                }
            }
            up(i,0,14)
            {
                up(j,0,14)
                {
                    up(k,0,4)
                    {
                        dis[i][j][k] = inf-1;
                    }
                }
            }
            dis[stx][sty][0]=0;
            queue q;
            q.push(Point(stx,sty,0,0));
            while(!q.empty())
            {
                Point ss=q.front();
                q.pop();
                Point ss2=ss;
                ss2.t++;
                if(ss2.t%p==0)
                {
                    ss2.di=(ss2.di-1+4)%4;
                }
                int dd=ss2.di;
                if(dis[ss.x][ss.y][dd]>dis[ss.x][ss.y][ss.di]+1)
                {
                    dis[ss.x][ss.y][dd]=dis[ss.x][ss.y][ss.di]+1;
                    q.push(Point(ss.x,ss.y,dd,ss2.t));
                }
    
                dd=(ss2.di-1+4)%4;
                if(dis[ss.x][ss.y][dd]>dis[ss.x][ss.y][ss.di]+1)
                {
                    dis[ss.x][ss.y][dd]=dis[ss.x][ss.y][ss.di]+1;
                    q.push(Point(ss.x,ss.y,dd,ss2.t));
                }
    
                dd=(ss2.di+1)%4;
                if(dis[ss.x][ss.y][dd]>dis[ss.x][ss.y][ss.di]+1)
                {
                    dis[ss.x][ss.y][dd]=dis[ss.x][ss.y][ss.di]+1;
                    q.push(Point(ss.x,ss.y,dd,ss2.t));
                }
    
                int x=ss.x+di[ss.di][0];
                int y=ss.y+di[ss.di][1];
                if(x>=0&&y>=0&&xdis[ss.x][ss.y][ss.di]+1)
                        {
                            dis[x][y][ss2.di]=dis[ss.x][ss.y][ss.di]+1;
                            q.push(Point(x,y,ss2.di,dis[x][y][ss2.di]));
                        }
            }
            int ans=inf;
            for(int i=0; i<4; i++)
                ans=min(ans,dis[enx][eny][i]);
            if(ans==inf-1)
                printf("YouBadbad\n");
            else
                printf("%d\n",ans);
        }
        return 0;
    }
    


     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved