4 4
....
..*@
..*@
.X*@

6 6
...#@.
@..*..
#*##..
..##*#
..X...
.@#...
  
  
   

  
  
   

    
   
   7
11
  
  
   
  
  
   


  
  
   

题意：类似推箱子游戏，三个箱子，三个目的地，求出人把三个箱子都推到目的地的最小步数，若没法完成就输出-1。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#define INF 100000000
using namespace std;
int n,m;
char map[9][9];
bool vis[8][8][8][8][8][8][8][8];
bool aim[8][8];
int dir[4][2]={
   {-1,0},{0,1},{1,0},{0,-1}};
struct point
{
    int x;
    int y;

};
struct node
{
    point p[4];
    int step;
};
node s,e;
bool ok(node &a)  //箱子是否全部进洞
{
    for (int i=1; i<=3; i++)
    {
        if(!aim[a.p[i].x][a.p[i].y])
            return false;
    }
    return true;
}
int bfs()
{
    memset(vis, false, sizeof(vis));
    memset(aim, false, sizeof(aim));
    for (int i=0; i<3; i++)
        aim[e.p[i].x][e.p[i].y]=true;  //目标状态
    
    queue<node>q;
    node temp;
    q.push(s);
    vis[s.p[0].x][s.p[0].y][s.p[1].x][s.p[1].y][s.p[2].x][s.p[2].y][s.p[3].x][s.p[3].y]=true;
    while (!q.empty())
    {
        s=q.front();
        q.pop();
        if(ok(s))
            return s.step;
        for (int i=0; i<4; i++)
        {
            temp=s;
            temp.p[0].x+=dir[i][0]; //人移动
            temp.p[0].y+=dir[i][1];
            int x=temp.p[0].x;
            int y=temp.p[0].y;
            if(x<0 || x>=n || y<0 || y>=m || map[x][y]=='#')
                continue;
            int j;
            //判断人是否遇到箱子
            for (j=1; j<=3; j++)
            {
                if(x==temp.p[j].x && y==temp.p[j].y)
                {
                    break;
                }
            }
            if(j==4) //人未遇到箱子
            {
                if(!vis[x][y][temp.p[1].x][temp.p[1].y][temp.p[2].x][temp.p[2].y][temp.p[3].x][temp.p[3].y])
                {
                    temp.step++;
                    vis[x][y][temp.p[1].x][temp.p[1].y][temp.p[2].x][temp.p[2].y][temp.p[3].x][temp.p[3].y]=true;
                    q.push(temp);
                }
            }
            else //遇到箱子，则移动箱子
            {
                //箱子移动后的坐标
                x+=dir[i][0];
                y+=dir[i][1];
                if(x<0 || x>=n || y<0 || y>=m || map[x][y]=='#')
                    continue;
                int k;
                for (k=1; k<=3; k++) //判断是否有其它箱子阻挡
                {
                    if(x==temp.p[k].x && y==temp.p[k].y)
                        break;
                }
                if(k==4) //没有其它箱子阻挡
                {
                    temp.p[j].x=x;
                    temp.p[j].y=y;
                    if(!vis[temp.p[0].x][temp.p[0].y][temp.p[1].x][temp.p[1].y][temp.p[2].x][temp.p[2].y][temp.p[3].x][temp.p[3].y])
                    {
                        temp.step++;
                        vis[temp.p[0].x][temp.p[0].y][temp.p[1].x][temp.p[1].y][temp.p[2].x][temp.p[2].y][temp.p[3].x][temp.p[3].y]=true;
                        q.push(temp);
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    int cnt,cnt2;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        cnt2=0;
        for (int i=0; i<n; i++)
        {
            scanf("%s",map[i]);
            for (int j=0; j<m; j++)
            {
                if(map[i][j]=='X')
                {
                    s.p[0].x=i;
                    s.p[0].y=j;
                }
                else if(map[i][j]=='*')
                {
                    s.p[++cnt].x=i;
                    s.p[cnt].y=j;
                }
                else if(map[i][j]=='@')
                {
                    e.p[cnt2].x=i;
                    e.p[cnt2++].y=j;
                }
                if(map[i][j]!='#')
                    map[i][j]='.';
            }
        }
        s.step=0;
        printf("%d\n",bfs());
    }
    return 0;
}