HDU - 1254 push bin (BFS + priority queue)

Pushing the box is a classic game. Today we are going to play a simple version. In an M*N room, there is a box and a porter. The job of the porter is to push the box to the designated position. Note that the porter can only push the box but not pull it, so if the box is pushed to a corner (as shown in Figure 2), the box can no longer be moved, If the box is pushed onto a wall, it can only move along the wall

Now given the structure of the room, the location of the box, the location of the porter and the location of the box to be pushed, please calculate how many squares the porter must push the box at least

Input
The first row of input data is an integer t (1 < = T < = 20), representing the number of test data. Then it is a group t test data. The first row of each group of test data is two positive integers m, n (2 < = m, n < = 7), representing the size of the room. Then it is a matrix of M rows and N columns, representing the layout of the room, where 0 represents the empty floor, 1 represents the wall, 2 represents the starting position of the box, 3 represents the position where the box is to be pushed, 4 represents the starting position of the porter
Output
For each group of test data, the output Porter needs to push at least how many boxes to push the box to the specified position. If the box cannot be pushed to the specified position, the output is - 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 idea: BFS + priority queue

bfs starts from man-made starting point, If the next step for a person is the coordinate of the box, it means that the box is found. The box coordinate is one grid ahead of the person's coordinate in the current search direction (that is, pushing a box, the box's direction is the same as the person's direction). Judge whether the box has reached the destination. If so, output the minimum steps of the box's movement, and if not, output - 1. The queue order should be determined according to the number of steps taken, so priority queue processing is used.

#include<stdio.h> 
#include<string.h> 
#include<queue> 
#include<algorithm> 
using namespace std;

int mp[9][9],book[9][9][9][9],n,m;
int nx[4][2]={1,0,0,-1,-1,0,0,1};

struct node
{
    int x,y,bx,by,step;
    bool friend operator < (const node &a, const node &b)
    {
        return a.step>b.step;//The greater than sign here indicates a Priority ratio of b large,The operator defined above is the less than sign, that is, the higher the priority, the smaller the value 
    }
} star;



int bfs()
{
    int tx,ty,tbx,tby;
    node now,next;
    priority_queue<node> Q;
    Q.push(star);
    while(!Q.empty())
    {
        now=Q.top();
        if(mp[now.bx][now.by]==3) return now.step;
        for(int i=0;i<4;i++)
        {
            tx=now.x+nx[i][0];
            ty=now.y+nx[i][1];
            if(tx>=0&&tx<n&&ty>=0&&ty<m&&mp[tx][ty]!=1)
            {
                next.x=tx;
                next.y=ty;
                next.bx=now.bx;
                next.by=now.by;
                next.step=now.step;
                if(tx==now.bx&&ty==now.by)
                {
                    tbx=tx+nx[i][0];
                    tby=ty+nx[i][1];
                    if(tbx>=0&&tbx<n&&tby>=0&&tby<m&&mp[tbx][tby]!=1)
                    {
                        next.bx=tbx;
                        next.by=tby;
                        next.step++;
                    }
                }
                if(book[tx][ty][next.bx][next.by]==0)
                {
                    book[tx][ty][next.bx][next.by]=1;
                    Q.push(next);
                }
            }
        }
        Q.pop();
    }
    return -1;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(book,0,sizeof(book));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%d",&mp[i][j]);
                if(mp[i][j]==4) {star.x=i;star.y=j;mp[i][j]=0;}
                if(mp[i][j]==2) {star.bx=i;star.by=j;mp[i][j]=0;}
            }
        }
        star.step=0;
        book[star.x][star.y][star.bx][star.by]=1;
        printf("%d\n",bfs());
    }
    return 0;
}

Tags: less

Posted on Fri, 01 May 2020 09:10:17 -0700 by hughesa