HDU1254 bfs

推箱子

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

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

Author

Ignatius.L & weigang Lee

代码:

/*
很明显是bfs,但需要再用一个bfs或dfs判断人能否走到箱子的后面去推他。用一个四维数组记录
人和箱子的位置状态,箱子可以重复经过某一位置但是人和箱子组成的四维的位置只能经过一次,
一定要注意搬运工可以有多个!!!
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int t,n,m;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct Lu
{
    int mp[8][8],sx,sy,ex,ey,cnt;
    bool vis[8][8][8][8];
}L;
struct po
{
    int x,y;
    bool vi[10][10];
};
int dfs(int x1,int y1,int p[8][8])
{
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(p[i][j]==4){    //找搬运工
                int x2=i,y2=j;
                queue<po>q;
                po p1,p2;
                memset(p1.vi,0,sizeof(p1.vi));
                p1.x=x2;p1.y=y2;p1.vi[x2][y2]=1;
                q.push(p1);
                while(!q.empty()){
                    p2=q.front();
                    q.pop();
                    if(p2.x==x1&&p2.y==y1)
                        return 1;
                    for(int i=0;i<4;i++){
                        int x=p2.x+dir[i][0],y=p2.y+dir[i][1];
                        if(x>=0&&x<n&&y>=0&&y<m&&p[x][y]!=1&&p[x][y]!=2&&!p2.vi[x][y]){
                            p1=p2;
                            p1.x=x;p1.y=y;p1.vi[x][y]=1;
                            q.push(p1);
                        }
                    }
                }
            }
        }
    }
    return 0;
}
int bfs()
{
    queue<Lu>q1;
    memset(L.vis,0,sizeof(L.vis));
    q1.push(L);
    Lu L1,L2;
    int cnt=0;
    while(!q1.empty()){
        L1=q1.front();
        q1.pop();
        if(L1.sx==L1.ex&&L1.sy==L1.ey)
            return L1.cnt;
        for(int i=0;i<4;i++){
            int x=L1.sx+dir[i][0],y=L1.sy+dir[i][1];
            if(x>=0&&x<n&&y>=0&&y<m&&L1.mp[x][y]!=1&&L1.mp[x][y]!=3&&dfs(x,y,L1.mp)){
                int a=L1.sx-dir[i][0],b=L1.sy-dir[i][1];
                if(a>=0&&a<n&&b>=0&&b<m&&L1.mp[a][b]!=1&&!L1.vis[a][b][L1.sx][L1.sy]){
                    L2=L1;
                    L2.vis[a][b][L1.sx][L1.sy]=1;
                    L2.sx=a;L2.sy=b;
                    L2.mp[x][y]=0;
                    L2.mp[L1.sx][L1.sy]=4;
                    L2.mp[a][b]=2;
                    L2.cnt=L1.cnt+1;
                    q1.push(L2);
                }
            }
        }
    }
    return -1;
}
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(L.mp,0,sizeof(L.mp));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%d",&L.mp[i][j]);
                if(L.mp[i][j]==2) {L.sx=i;L.sy=j;}
                if(L.mp[i][j]==3) {L.ex=i;L.ey=j;}
            }
        }
        int ans=bfs();
        cout<<ans<<endl;
    }
    return 0;
}
时间: 01-13

HDU1254 bfs的相关文章

hdu1254(bfs+dfs)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1254 分析: 真正移动的是箱子,但是要移动箱子需要满足几个条件. 1.移动方向上没有障碍. 2.箱子后方没有障碍. 3.人可以到达箱子后方的地方.这里dfs或bfs都可以实现 按条件搜索即可. #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include &l

hdu1254 推箱子 搜索水题(bfs+bfs)

题意就不多说了 我使用bfs+bfs做的      听说bfs+dfs也能做   我觉得都差不多     我就说一下bfs+bfs 注意:箱子走过的地方还能再走   但从同一方向过来的就不能再走了    所以  标记时  得同时记录箱子和方向    方向可以根据人的位置来判断 箱子能往某一方向推的两个条件是: 目的地是空的    人能推动及人能到达要推的地方 然后按照一般广搜做就行 #include<stdio.h> #include<string.h> #include<q

[hdu 2102]bfs+注意INF

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102 感觉这个题非常水,结果一直WA,最后发现居然是0x3f3f3f3f不够大导致的--把INF改成INF+INF就过了. #include<bits/stdc++.h> using namespace std; bool vis[2][15][15]; char s[2][15][15]; const int INF=0x3f3f3f3f; const int fx[]={0,0,1,-1};

BFS+康托展开(洛谷1379 八数码难题)

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字.棋盘中留有一个空格,空格用0来表示.空格周围的棋子可以移到空格中.要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变. 输入格式: 输入初试状态,一行九个数字,空格用0表示 输出格式: 只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据) 输入样例#1: 2831

Sicily 1444: Prime Path(BFS)

题意为给出两个四位素数A.B,每次只能对A的某一位数字进行修改,使它成为另一个四位的素数,问最少经过多少操作,能使A变到B.可以直接进行BFS搜索 1 #include<bits/stdc++.h> 2 using namespace std; 3 4 bool isPrime(int n){//素数判断 5 if(n == 2 || n == 3) return true; 6 else{ 7 int k = sqrt(n) + 1; 8 for(int i = 2; i < k; i

HDU 5925 Coconuts 【离散化+BFS】 (2016CCPC东北地区大学生程序设计竞赛)

Coconuts Time Limit: 9000/4500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 524    Accepted Submission(s): 151 Problem Description TanBig, a friend of Mr. Frog, likes eating very much, so he always has dreams abou

POJ3967Ideal Path[反向bfs 层次图]

Ideal Path Time Limit: 10000MS   Memory Limit: 65536K Total Submissions: 1754   Accepted: 240 Description New labyrinth attraction is open in New Lostland amusement park. The labyrinth consists of n rooms connected by m passages. Each passage is colo

胜利大逃亡(续)(状态压缩bfs)

胜利大逃亡(续) Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7357    Accepted Submission(s): 2552 Problem Description Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带

邻接表实现Dijkstra算法以及DFS与BFS算法

//============================================================================ // Name : ListDijkstra.cpp // Author : fffff // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //==========================