HDU 3309 Roll The Cube(bfs)
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;
}