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

HDU 1732 Push Box(DFS+BFS)

本文由 Ocrosoft 于 2016-07-13 11:22:43 发表

Push Box

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 1285    Accepted Submission(s): 496

Problem Description
Push Box is a classic puzzle game. This game play in a grid, there are five types of block in it, the player, the box, the hole, empty place, and the wall. In every step, player can move up, down, left, or right, if the target place is empty. Moreover, if a box in the target place, and the next place in that direction is empty, player can move to the target place, and then push the box to the next place. Remember, both of the player and boxes can’t move out of the grid, or you may assume that there is a wall suround the whole grid. The objective of this game is to push every box to a hole. Now, your problem is to find the strategy to achieve the goal with shortest steps, supposed there are exactly three boxes.
 

Input
The input consists of several test cases. Each test case start with a line containing two number, n, m(1 < n, m ≤ 8), the rows and the columns of grid. Then n lines follow, each contain exact m characters, representing the type of block in it. (for empty place, X for player, * for box, # for wall, @ for hole). Each case contain exactly one X, three *, and three @. The input end with EOF.
 

Output
You have to print the length of shortest strategy in a single line for each case. (-1 if no such strategy)
 

Sample Input
	
4 4 .... ..*@ ..*@ .X*@ 6 6 ...#@. @..*.. #*##.. ..##*# ..X... .@#...
 

Sample Output
	
7 11
 

Solution

这箱子有毒!!!

题意:有3个箱子,这次问的是把箱子推好,人最少走几步。

跟推箱子那题一样,但是开状态需要开8维,推箱子的时候要再来一个for循环推3个箱子,其他还好。

为什么有毒呢???WA了两天,错的竟然是读入!读入!!读入!!!

实在找不出哪里有问题。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int n,m;
char mp[8][8];
int reach[8][8];
int dir[4][2]={0,1,1,0,0,-1,-1,0};
bool vis[8][8][8][8][8][8][8][8];//三个箱子的位置和人的位置,1677216
struct Point//人的BFS用
{
    int x,y;
    int step;
    bool check()
    {
        if(x<0||y<0||x>=n||y>=m)return 0;//越界
        if(mp[x][y]=='#')return 0;
        return 1;//可以走
    }
};
struct node
{
    int px,py;//人的位置
    int bx[3],by[3];//箱子的位置
    int step;
    bool check(int k)
    {
        if(bx[k]<0||by[k]<0||bx[k]>=n||by[k]>=m)return 0;//越界
        if(mp[bx[k]][by[k]]=='#')return 0;//墙
        return 1;
    }
    bool operator <(const node a) const
    {
        return step>a.step;
    }
};
void bfs_p(node no)//找到人能走到的所有位置
{
    Point t,tt;
    t.x=no.px,t.y=no.py,t.step=0;
    memset(reach,-1,sizeof(reach));
    reach[t.x][t.y]=0;
    queue<Point> q;
    q.push(t);
    while(!q.empty())
    {
        t=q.front(),q.pop();
        for(int i=0;i<4;i++)
        {
            tt=t,tt.step++,tt.x+=dir[i][0],tt.y+=dir[i][1];
            if(!tt.check())continue;//越界或者墙
            if(reach[tt.x][tt.y]>=0)continue;//访问过
            if((tt.x==no.bx[0]&&tt.y==no.by[0])||
               (tt.x==no.bx[1]&&tt.y==no.by[1])||
               (tt.x==no.bx[2]&&tt.y==no.by[2])
               )continue;//走的位置是箱子
            reach[tt.x][tt.y]=tt.step;
            q.push(tt);
        }
    }
}
int bfs_b(node st)//箱子
{
    node t,tt;
    int px,py;//人需要走到的位置
    priority_queue<node> q;
    ms(vis);
    q.push(st);
    while(!q.empty())
    {
        t=q.top(),q.pop();
        if(mp[t.bx[0]][t.by[0]]=='@'&&
           mp[t.bx[1]][t.by[1]]=='@'&&
           mp[t.bx[2]][t.by[2]]=='@')return t.step;
        bfs_p(t);
        for(int i=0;i<3;i++)//3个箱子
        {
            for(int j=0;j<4;j++)//4个方向
            {
                tt=t;
                tt.bx[i]+=dir[j][0],tt.by[i]+=dir[j][1];
                px=t.bx[i]-dir[j][0],py=t.by[i]-dir[j][1];
                if(!tt.check(i))continue;//越界或者墙
                if(reach[px][py]==-1)continue;//-1表示无法到达
                if(px<0||px>=n||py<0||py>=m)continue;//人要走到的位置在界外
                if((tt.bx[i]==t.bx[0]&&tt.by[i]==t.by[0])||
                   (tt.bx[i]==t.bx[1]&&tt.by[i]==t.by[1])||
                   (tt.bx[i]==t.bx[2]&&tt.by[i]==t.by[2])
                   )continue;//推向的方向是箱子
                if(vis[tt.bx[0]][tt.by[0]][tt.bx[1]][tt.by[1]][tt.bx[2]][tt.by[2]][tt.px][tt.py])continue;
                vis[tt.bx[0]][tt.by[0]][tt.bx[1]][tt.by[1]][tt.bx[2]][tt.by[2]][tt.px][tt.py]=1;
                tt.step+=reach[px][py]+1;//推箱子还要一步
                tt.px=t.bx[i],tt.py=t.by[i];//人走到箱子原来的地方
                q.push(tt);
            }
        }
    }
    return -1;
}
int main()
{
/*
    while(cin>>n>>m)
    {
        node st;
        for(int i=0; i<n; i++)cin>>mp[i];
        int tmp=0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(mp[i][j]=='*')st.bx[tmp]=i,st.by[tmp++]=j,mp[i][j]='.';
				else if(mp[i][j]=='X')mp[i][j]='.',st.px=i,st.py=j;
            }
        }
        st.step=0;
        printf("%d\n",bfs_b(st));
    }
*/
    while(cin>>n>>m)
	{
		node start;
		int k=0;
		for( int i = 0; i < n; i ++ )
		{
			getchar();
			for ( int j = 0; j < m; j ++ )
			{
				scanf("%c",&mp[i][j]);
				if(mp[i][j]=='*')start.bx[k]=i,start.by[k++]=j,mp[i][j]='.';
				else if(mp[i][j]=='X')mp[i][j]='.',start.px=i,start.py=j;
			}
		}
		start.step = 0;
		printf("%d\n",bfs_b(start) );
	}
    return 0;
}


 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 1732 Push Box(DFS+BFS)

点赞 (0)or拍砖 (0)

评论 抢沙发

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