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.
'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(*).
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.
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; }
?
?
更多文章、技術(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ì)您有幫助就好】元
