首页 > ACM题库 > HDU-杭电 > HDU 1254 推箱子-DFS-[解题报告] C++
2013
12-04

HDU 1254 推箱子-DFS-[解题报告] C++

推箱子

问题描述 :

推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.

现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.

输入:

输入数据的第一行是一个整数T(1<=T<=20),代表测试数据的数量.然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2<=M,N<=7),代表房间的大小,然后是一个M行N列的矩阵,代表房间的布局,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代表箱子要被推去的位置,4代表搬运工的起始位置.

输出:

对于每组测试数据,输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置,如果不能推到指定位置则输出-1.

样例输入:

1
5 5
0 3 0 0 0
1 0 1 4 0
0 0 1 0 0
1 0 2 0 0
0 0 0 0 0

样例输出:

4

我写的第一道感觉比较难的搜索

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1254

首先要推箱子的话要满足人能够在箱子旁边,而且人的对面也是可通的。

我的思路:

先判断箱子周围的空地(即可能能被人推到的格子),然后判断人是否能够达到即将推箱子的位置,在这里我用BFS嵌套DFS,其中BFS用优先权队列进行维护,每次取步数最少的当前箱子的位置,然后对于当前箱子可以到达的位置来说,DFS人,判断人能否到达推箱子的位置。

在这里,重要的一点是,对于一个当前的箱子,可以从不同的方向推,所以我用visit[x][y][z][k]判断对于当前的x,y格子里的箱子来说,是否已经被在z,k格子里的人推过,推过为1。

代码运行时间0MS 

代码实现如下:

#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<fstream>

using namespace std;
class node
{
    public:
        int x;
        int y;
        int step;
        int people_x;
        int people_y;
        friend bool operator <(node a,node b)
        {
              return a.step>b.step;
        }
}cur,next;
priority_queue<node>q;
int d[4][2]={1,0,-1,0,0,1,0,-1};
int visit[10][10][10][10];
int visit2[10][10];
int map[10][10];
bool flag;
int m,n;
int start1_x,start1_y;
int start2_x,start2_y;
int end_x,end_y;

void  init()
{
        memset(visit,0,sizeof(visit));
        memset(map,1,sizeof(map));
        memset(visit2,0,sizeof(visit2));
        flag=0;

}
int flag1=0;
int cur_x,cur_y;
bool dfs(int x,int  y,int cur_x, int cur_y ,int people_x,int people_y)
{
        visit2[x][y]=1;

        if(x==people_x&&y==people_y) {flag1=1;return true;}
        if(flag1==0)
        for(int i=0;i<4;i++)
        {
             int xx=x+d[i][0];
             int yy=y+d[i][1];
             if(xx>m||xx<1||yy>n||yy<1||map[xx][yy]==1||visit2[xx][yy]||(xx==cur_x&&yy==cur_y)) continue;
              
             dfs(xx,yy,cur_x,cur_y,people_x,people_y);
             if(flag1) return true;
        }
        return false;
       
}
void bfs()
{
       while(!q.empty())
       {
               cur=q.top();
               q.pop();
               if(cur.x==end_x&&cur.y==end_y)
               {
                       cout<<cur.step<<endl;
                       flag=1;
                       break;
               }
               for(int i=0;i<4;i++)
               {
                      memset(visit2,0,sizeof(visit2));
                      flag1=0;
                      int  x=cur.x+d[i][0];
                      int  y=cur.y+d[i][1];
                  
                      if(x>m||x<1||y>n||y<1||map[x][y]==1) continue;
                       next.x=x;next.y=y;
                       next.people_x=cur.x;
                       next.people_y=cur.y;
                       next.step=cur.step+1;
                      if(i==0)
                        if(map[cur.x-1][cur.y]!=1&&dfs(cur.x-1,cur.y,cur.x,cur.y,cur.people_x,cur.people_y)&&visit[x][y][cur.x-1][cur.y]==0)
                              {
                                     visit[x][y][cur.x-1][cur.y]=1;
                                     q.push(next);
                              }
                      if(i==1)
                        if(map[cur.x+1][cur.y]!=1&&dfs(cur.x+1,cur.y,cur.x,cur.y,cur.people_x,cur.people_y)&&visit[x][y][cur.x+1][cur.y]==0)
                              {
                                     visit[x][y][cur.x+1][cur.y]=1;
                                     q.push(next);
                              }
                      if(i==2)
                        if(map[cur.x][cur.y-1]!=1&&dfs(cur.x,cur.y-1,cur.x,cur.y,cur.people_x,cur.people_y)&&visit[x][y][cur.x][cur.y-1]==0)
                                {
                                        visit[x][y][cur.x][cur.y-1]=1;
                                        q.push(next);
                                }
                      if(i==3)
                        if(map[cur.x][cur.y+1]!=1&&dfs(cur.x,cur.y+1,cur.x,cur.y,cur.people_x,cur.people_y)&&visit[x][y][cur.x][cur.y+1]==0)
                               {
                                       visit[x][y][cur.x][cur.y+1]=1;
                                       q.push(next);
                               }

               }
       }
}
int main()
{
       int t;
       cin>>t;
       while(t--)
       {
               init();
               while(!q.empty()) q.pop();
             scanf("%d%d",&m,&n);

             for(int i=1;i<=m;i++)
                     for(int j=1;j<=n;j++)
                     {
                             scanf("%d",&map[i][j]);
                             if(map[i][j]==2)
                             {
                                     start1_x=i;
                                     start1_y=j;
                             }
                             if(map[i][j]==3)
                             {
                                     end_x=i;
                                     end_y=j;
                             }
                             if(map[i][j]==4)
                             {
                                     start2_x=i;
                                     start2_y=j;
                             }
                     }
             cur.x=start1_x;
             cur.y=start1_y;
             cur.step=0;
             cur.people_x=start2_x;
             cur.people_y=start2_y;

             q.push(cur);
             bfs();
             if(flag==0) cout<<"-1"<<endl;
       } 
   return 0;
}

  

 

 


, ,
  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  4. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks