亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu 3309 Roll The Cube ( bfs )

系統(tǒng) 2151 0

Roll The Cube

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 345????Accepted Submission(s): 127

?

Problem Description
This is a simple game.The goal of the game is to roll two balls to two holes each.
'B' -- ball
'H' -- hole
'.' -- land
'*' -- wall
Remember when a ball rolls into a hole, they(the ball and the hole) disappeared, that is , 'H' + 'B' = '.'.
Now you are controlling two balls at the same time.Up, down , left , right --- once one of these keys is pressed, balls exist roll to that direction, for example , you pressed up , two balls both roll up.
A ball will stay where it is if its next point is a wall, and balls can't be overlap.
Your code should give the minimun times you press the keys to achieve the goal.
?

?

Input
First there's an integer T(T<=100) indicating the case number.
Then T blocks , each block has two integers n , m (n , m <= 22) indicating size of the map.
Then n lines each with m characters.
There'll always be two balls(B) and two holes(H) in a map.
The boundary of the map is always walls(*).
?

?

Output
The minimum times you press to achieve the goal.
Tell me "Sorry , sir , my poor program fails to get an answer." if you can never achieve the goal.
?

?

Sample Input
4 6 3 *** *B* *B* *H* *H* *** 4 4 **** *BB* *HH* **** 4 4 **** *BH* *HB* **** 5 6 ****** *.BB** *.H*H* *..*.* ******
?

?

Sample Output
3 1 2 Sorry , sir , my poor program fails to get an answer.
?

?

Author
MadFroG
?

?

Source


思路:
bfs,用兩個(gè)球的位置來(lái)判重,其他的直接模擬就ok了。最好將球和洞分開(kāi)看,還有就是注意一下兩個(gè)球不能在同一個(gè)位置。

代碼:
      #include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define maxn 25

#define INF 0x3f3f3f3f

using namespace std;



int n,m,ans;

int sx[2],sy[2];

int dx[]= {-1,1,0,0};

int dy[]= {0,0,-1,1};

bool vis[maxn][maxn][maxn][maxn];

char mp[maxn][maxn];

char s[maxn];

struct Node

{

    int x[2],y[2],step;

    int b[2],h[2];   // 球 洞  球是否進(jìn)洞和洞是否被求填滿分開(kāi)看

} cur,now;

queue<Node>q;



bool bfs()

{

    int i,j,t,flag;

    memset(vis,0,sizeof(vis));

    while(!q.empty()) q.pop();

    cur.x[0]=sx[0],cur.y[0]=sy[0];

    cur.x[1]=sx[1],cur.y[1]=sy[1];

    cur.h[0]=cur.h[1]=0;

    cur.b[0]=cur.b[1]=0;

    cur.step=0;

    vis[sx[0]][s[0]][sx[1]][sy[1]]=1;

    q.push(cur);

    while(!q.empty())

    {

        now=q.front();

        q.pop();

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

        {

            cur=now;

            for(j=0; j<2; j++)

            {

                if(cur.b[j]) continue ;

                cur.x[j]+=dx[i];

                cur.y[j]+=dy[i];

                if(mp[cur.x[j]][cur.y[j]]=='*')

                {

                    cur.x[j]-=dx[i];

                    cur.y[j]-=dy[i];

                }

            }

            if(vis[cur.x[0]][cur.y[0]][cur.x[1]][cur.y[1]]||cur.x[0]==cur.x[1]&&cur.y[0]==cur.y[1]&&cur.b[0]+cur.b[1]==0) continue ;

            cur.step++;

            vis[cur.x[0]][cur.y[0]][cur.x[1]][cur.y[1]]=1;

            flag=1;

            for(j=0; j<2; j++)

            {

                t=mp[cur.x[j]][cur.y[j]];

                if(t<2&&!cur.h[t]) cur.b[j]=1,cur.h[t]=1;

                if(!cur.b[j]) flag=0;

            }

            if(flag)

            {

                ans=cur.step;

                return true ;

            }

            q.push(cur);

        }

    }

    return false ;

}

int main()

{

    int i,j,t,cnt1,cnt2;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        cnt1=cnt2=0;

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

        {

            scanf("%s",s);

            for(j=1; j<=m; j++)

            {

                mp[i][j]=s[j-1];

                if(mp[i][j]=='H') mp[i][j]=cnt1++;

                else if(mp[i][j]=='B') sx[cnt2]=i,sy[cnt2]=j,cnt2++;

            }

        }

        if(bfs()) printf("%d\n",ans);

        else printf("Sorry , sir , my poor program fails to get an answer.\n");

    }

    return 0;

}


    


?

?

hdu 3309 Roll The Cube ( bfs )


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 久久视频这里只精品3国产 久久视频这里只有精品 | 亚洲精品不卡午夜精品 | 成人久久精品一区二区三区 | 色老头一区二区三区 | 国产精品tv | 香蕉视频毛片 | 波多野结衣久久高清免费 | 深夜a| 97精品久久天干天天蜜 | 精品在线播放 | 欧美成人私人视频88在线观看 | 亚洲欧美日韩在线观看你懂的 | 天天射天天干天天插 | 成人18免费网 | 羞羞网站在线免费观看 | 日本综合视频 | 国产亚洲人成a在线v网站 | 一区二区三区在线免费观看视频 | 成 人 a v免费视频 | 毛片一级免费 | 欧美精品成人 | 99精彩免费观看 | 2021成人国产精品 | 久久国产亚洲观看 | 亚洲一级毛片免费在线观看 | 欧美特欧美特级一片 | 女人洗澡一级毛片一级毛片 | 日本高清在线一区二区三区 | 国产精品视频第一区二区 | 国内精品伊人久久大香线焦 | 60岁妇女毛片 | 曰本一级毛片免费播放 | 天天拍天天干 | 国产精品久久久久9999高清 | 四虎最新永久免费网址 | 欧美国产精品亚洲精品第一区 | 日本不卡高清免费 | 中文字幕在线观看日本 | 九九热精品在线观看 | 欧美成人久久 | 精彩视频一区二区三区 |