2014
03-16

# Roll The Cube

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.

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(*).

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(*).

4
6 3
***
*B*
*B*
*H*
*H*
***

4 4
****
*BB*
*HH*
****

4 4
****
*BH*
*HB*
****

5 6
******
*.BB**
*.H*H*
*..*.*
******

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

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
char map[25][25];
bool vis[25][25][25][25];
bool mark[25][25][25][25];
int dir[4][2]=  {{1,0},{0,1},{-1,0},{0,-1}};
int flag,ans;
struct node
{
int len;
int x[2],y[2];
int holex,holey;
int step;int find;

} s_pos;
bool cheack(int x,int y){   return x>=0&&x<=n+1&&y>=0&y<=m+1;     }
void bfs()
{
queue<node > q;
q.push(s_pos);
memset(vis,0,sizeof(vis));
memset(mark,0,sizeof(mark));
vis[s_pos.x[0]][s_pos.y[0]][s_pos.x[1]][s_pos.y[1]]=true;

while(!q.empty())
{
node now = q.front();
q.pop();

if(now.find){
if(map[now.x[0]][now.y[0]]=='H'&&(now.x[0]!=now.holex||now.y[0]!=now.holey))
{
flag=1;   ans=now.step;
return ;
}
}
else{
if(map[now.x[0]][now.y[0]]=='H'&&map[now.x[1]][now.y[1]]=='H'&&(now.x[0]!=now.x[1]||now.y[0]!=now.y[1]))
{
flag=1;   ans=now.step;
return ;
}
if(map[now.x[0]][now.y[0]]=='H')
{

now.holex=now.x[0];  now.holey=now.y[0];
now.x[0]=now.x[1];   now.y[0]=now.y[1];

mark[now.holex][now.holey][now.x[0]][now.y[0]]=true;
now.find=1;  now.len--;
}
if(map[now.x[1]][now.y[1]]=='H')
{
now.holex=now.x[1];  now.holey=now.y[1];
mark[now.holex][now.holey][now.x[0]][now.y[0]]=true;
now.find=1;  now.len--;
}
}

for(int i=0; i<4; i++)
{
node next=now;
next.step+=1;
for(int j=0; j<next.len; j++)
next.x[j]+=dir[i][0],  next.y[j]+=dir[i][1];

if(next.len==2)
{
if(cheack(next.x[0],next.y[0])&&cheack(next.x[1],next.y[1]))
{
if(map[next.x[0]][next.y[0]]=='*'&&map[next.x[1]][next.y[1]]=='*')            continue;
if(map[next.x[0]][next.y[0]]=='*'&&next.x[1]==now.x[0]&&next.y[1]==now.y[0])  continue;
if(map[next.x[1]][next.y[1]]=='*'&&next.x[0]==now.x[1]&&next.y[0]==now.y[1])  continue;

if(map[next.x[0]][next.y[0]]=='*'){
next.x[0]=now.x[0],   next.y[0]=now.y[0];
}
if(map[next.x[1]][next.y[1]]=='*'){
next.x[1]=now.x[1],   next.y[1]=now.y[1];
}

if(!vis[next.x[0]][next.y[0]][next.x[1]][next.y[1]])
{
vis[next.x[0]][next.y[0]][next.x[1]][next.y[1]]=true;
q.push(next);
}
}
}
else
{

if(cheack(next.x[0],next.y[0])&&!mark[next.holex][next.holey][next.x[0]][next.y[0]])
{

mark[next.holex][next.holey][next.x[0]][next.y[0]]=true;
if(map[next.x[0]][next.y[0]]=='*')            continue;
q.push(next);

}
}
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;

for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++) map[i][j]='*';

for(int i=1; i<=n; i++) cin>>map[i]+1;

s_pos.len=0;  s_pos.holex=100;s_pos.holey=100;  s_pos.step=0;  s_pos.find=0;

for(int i=0;i<=n+1;i++)
map[i][m+1]='*';

for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
if(map[i][j]=='B')
{
s_pos.x[s_pos.len]=i,s_pos.y[s_pos.len]=j;
s_pos.len++;
}
flag=0;  ans=0x7fffffff;
bfs();
if(flag)
cout<<ans<<endl;
else
cout<<"Sorry , sir , my poor program fails to get an answer."<<endl;

}
return 0;

}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

3. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。