[HDU 1254] 推箱子

时间：2021-05-10 15:53:31

推箱子

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5343    Accepted Submission(s): 1503 

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

搜索水题、

百度了下，目测网上基本都是搜索套搜索。。。。。

代码可能会有错、没怎么检查就水过了。

应该容易懂、不注释了 - -

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

#define INF 0x7ffffff

#define N 8

struct node

{

    int px,py;

    int bx,by;

    int step;

};

int ans;

int flag;

int n,m;

int px,py;

int bx,by;

int mpt[N][N];

int vis1[N][N];

int vis2[N][N][N][N];

int dir[][]={,-,,,-,,,};

bool judge(int x,int y)

{

    if(x>= && x<=n && y>= && y<=m && mpt[x][y]!=) return ;

    return ;

}

void bfs()

{

    queue<node> q;

    node now,next;

    now.bx=bx;

    now.by=by;

    now.px=px;

    now.py=py;

    now.step=;

    vis2[now.bx][now.by][now.px][now.py]=;

    q.push(now);

    while(!q.empty())

    {

        now=q.front();

        q.pop();

        if(mpt[now.bx][now.by]==)

        {

            ans=min(ans,now.step);

            return;

        }

        for(int i=;i<;i++)

        {

            next=now;

            next.px+=dir[i][];

            next.py+=dir[i][];

            if(!judge(next.px,next.py)) continue;

            if(next.bx==next.px && next.by==next.py)

            {

                next.step++;

                next.bx+=dir[i][];

                next.by+=dir[i][];

                if(!judge(next.bx,next.by)) continue;

            }

            if(!vis2[next.bx][next.by][next.px][next.py])

            {

                vis2[next.bx][next.by][next.px][next.py]=;

                q.push(next);

            }

        }

    }

}

void dfs(int x,int y)

{

    if(mpt[x][y]==)

    {

        flag=;

        return;

    }

    if(flag) return;

    for(int i=;i<;i++)

    {

        int tx=x+dir[i][];

        int ty=y+dir[i][];

        if(judge(tx,ty) && mpt[tx][ty]!= && !vis1[tx][ty])

        {

            vis1[tx][ty]=;

            dfs(tx,ty);

            vis1[tx][ty]=;

        }

    }

}

int main()

{

    int T,i,j;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(i=;i<=n;i++)

        {

            for(j=;j<=m;j++)

            {

                scanf("%d",&mpt[i][j]);

                if(mpt[i][j]==)

                {

                    bx=i;

                    by=j;

                }

            }

        }

        ans=INF;

        for(i=;i<;i++)

        {

            px=bx+dir[i][];

            py=by+dir[i][];

            if(judge(px,py))

            {

                flag=;

                memset(vis1,,sizeof(vis1));

                dfs(px,py);

                if(flag)

                {

                    memset(vis2,,sizeof(vis2));

                    bfs();

                }

            }

        }

        if(ans==INF)

            cout<<-<<endl;

        else

            cout<<ans<<endl;

    }

    return ;

}

相关文章