首页 > 搜索 > BFS搜索 > HDU 3309-Roll The Cube-模拟-[解题报告]HOJ
2014
03-16

HDU 3309-Roll The Cube-模拟-[解题报告]HOJ

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.

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3309

模型很容易发现是BFS。。但是模拟过程还是蛮蛋疼的。

我是分成两种方式BFS的。一种是 两个球一起走,另一种是 一个球单独跑(另外一个球已经进坑)。最好开两个4维的标记数组。一个四维的标记两个球一起跑时的。

另一个4维的前面两个标记金坑的坐标(一开始没这么搞,开的二维的。。一直错。找不到原因)。后面两个标记另一个球的坐标。代码写得超级烂。。。有很多 不必要点。

下面是 AC代码 :

#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;

}

参考:http://blog.csdn.net/w00w12l/article/details/7893326


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