浙江财经大学
信息管理与工程学院

HDU 1254 推箱子(BFS+BFS)

本文由 Ocrosoft 于 2016-07-08 21:42:19 发表

推箱子

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7107    Accepted Submission(s): 2024

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

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

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

Sample Input
	
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
 

Sample Output
	
4
 

Solution

题意:经典的推箱子,箱子只有一个,问能不能推到目标点,能则输出箱子移动的最小步数。

因为问的是最小步数,所以用BFS,但是箱子是要人推的,所以要用一个BFS来判断人能不能走到推的位置。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int n,m;
int mp[10][10];
bool reach[10][10];
bool vis[10][10][10][10];
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
struct Point
{
    int x,y;
    int step;
    bool check()
    {
        if(x<0||y<0||x>=n||y>=m)return 0;
        if(mp[x][y]!=0)return 0;
        if(reach[x][y])return 0;
        return 1;
    }
    bool check_b(Point p)
    {
        if(x<0||y<0||x>=n||y>=m)return 0;
        if(mp[x][y]!=0)return 0;
        if(vis[x][y][p.x][p.y])return 0;
        return 1;
    }
} p,e,b; //person,end,box
void bfs_p()
{
    queue<Point> q;
    ms(reach);
    q.push(p);
    Point t,tt;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        reach[t.x][t.y]=1;
        for(int i=0; i<4; i++)
        {
            tt.x=t.x+dir[i][0];
            tt.y=t.y+dir[i][1];
            if(tt.check())q.push(tt);
        }
    }
}
int bfs_b()
{
    ms(vis);
    queue<Point> q;
    q.push(b);
    q.push(p);
    Point t,tt;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        p=q.front();
        q.pop();
        if(t.x==e.x&&t.y==e.y)return t.step;
        vis[t.x][t.y][p.x][p.y]=1;
        mp[t.x][t.y]=2;
        bfs_p();
        mp[t.x][t.y]=0;
        for(int i=0; i<4; i++)
        {
            tt.x=t.x+dir[i][0];
            tt.y=t.y+dir[i][1];
            tt.step=t.step+1;
            if(tt.check_b(t)&&reach[t.x-dir[i][0]][t.y-dir[i][1]])
            {
                q.push(tt);
                q.push(t);
            }
        }
    }
    return -1;
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        cin>>n>>m;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                cin>>mp[i][j];
                if(mp[i][j]==2)
                    b.x=i,b.y=j,b.step=0;
                else if(mp[i][j]==3)
                    e.x=i,e.y=j,mp[i][j]=0;
                else if(mp[i][j]==4)
                    p.x=i,p.y=j,mp[i][j]=0;
            }
            printf("%d\n",bfs_b());
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 1254 推箱子(BFS+BFS)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址