# Roll The Cube

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 680    Accepted Submission(s): 272

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.
BFS 要注意一个球进了洞，那么这个球和洞都消失了，变成了.只剩另一个球了。#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <queue>

using namespace std;
char a[105][105];
int dp[25][25][25][25];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
struct Node
{
int x1,y1,x2,y2;
int time;
int tag1;
int tag2;
int X1,Y1,X2,Y2;
Node(){};
Node(int x1,int y1,int x2,int y2,int time,int tag1,int tag2)
{
this->x1=x1;
this->y1=y1;
this->x2=x2;
this->y2=y2;
this->time=time;
this->tag1=tag1;
this->tag2=tag2;
}
};
queue<Node> q;
int BFS(int x1,int y1,int x2,int y2)
{

q.push(Node(x1,y1,x2,y2,0,0,0));
Node term;
dp[x1][y1][x2][y2]=1;
int xx1,yy1,xx2,yy2;
int xo1,yo1,xo2,yo2;
while(!q.empty())
{
term=q.front();
q.pop();
if(a[term.x1][term.y1]=='H')
{
if(term.tag2==0)
term.tag1=1;
if(term.tag2)
{
if(term.x1!=term.x2)
term.tag1=1;
if(term.y1!=term.y2)
term.tag1=1;
}

}
if(a[term.x2][term.y2]=='H')
{
if(term.tag1==0)
term.tag2=1;
if(term.tag1)
{
if(term.x1!=term.x2)
term.tag2=1;
if(term.y1!=term.y2)
term.tag2=1;
}
}
if(term.tag1&&term.tag2)
{
return term.time;
}
for(int i=0;i<4;i++)
{
xo1=xx1=term.x1+dir[i][0];
xo2=xx2=term.x2+dir[i][0];
yo1=yy1=term.y1+dir[i][1];
yo2=yy2=term.y2+dir[i][1];
if(term.tag1!=0)
{
xo1=xx1=term.x1;
yo1=yy1=term.y1;
}
if(term.tag2!=0)
{
xo2=xx2=term.x2;
yo2=yy2=term.y2;
}
if(!term.tag1)
{
if(a[xx1][yy1]=='*') {xx1=term.x1;yy1=term.y1;}
else if(xx1==term.x2&&yy1==term.y2)
{
if(a[xo2][yo2]=='*')
{xx1=term.x1;yy1=term.y1;}
}
}
if(!term.tag2)
{
if(a[xx2][yy2]=='*') {xx2=term.x2;yy2=term.y2;}
else if(xx2==term.x1&&yy2==term.y1)
{
if(a[xo1][yo1]=='*')
{
xx2=term.x2;
yy2=term.y2;
}
}
}
if(dp[xx1][yy1][xx2][yy2]) continue;
dp[xx1][yy1][xx2][yy2]=1;
q.push(Node(xx1,yy1,xx2,yy2,term.time+1,term.tag1,term.tag2));
}
}
return -1;
}
int main()
{
int t;
scanf("%d",&t);
int x1,y1,x2,y2;

while(t--)
{
int tag1=false;
int tag2=false;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",a[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='B')
{
if(!tag1) {x1=i;y1=j;tag1=true;continue;}
if(!tag2) {x2=i;y2=j;tag2=true;}
}
}
}
while(!q.empty())
q.pop();
memset(dp,0,sizeof(dp));
int ans=BFS(x1,y1,x2,y2);
if(ans==-1)
{
printf("Sorry , sir , my poor program fails to get an answer.\n");
}
else
printf("%d\n",ans);
}
return 0;
}```

0 条评论

## 相关文章

### HDU 3367 Pseudoforest(Kruskal)

Pseudoforest Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/655...

3015

### HDUOJ ------1398

http://acm.hdu.edu.cn/showproblem.php?pid=1398 Square Coins Time Limit: 2000/100...

2766

### HDUOJ--------Text Reverse

Text Reverse Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65...

3427

### HDU 3388 Coprime（容斥原理+二分）

Coprime Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

3325

### HDUOJ----Coin Change

Coin Change Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

28711

### HDUOJ---The number of divisors(约数) about Humble Numbers

The number of divisors(约数) about Humble Numbers Time Limit: 2000/1000 MS (Java/O...

3425

### POJ 2773 Happy 2006（容斥原理+二分）

Happy 2006 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1...

2967

### POJ-1458 Common Subsequence（线性动规，最长公共子序列问题）

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submis...

3277

### HDU 3578 Greedy Tino（双塔DP）

Greedy Tino Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

3465

### HDUOJ-----X问题

X问题 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

2717