题目链接：http://icpc.njust.edu.cn/Problem/Hdu/1732/
题目就是推箱子游戏，有三个箱子和三个洞，最终目标状态就是三个箱子到三个洞中，所以我们搜索的状态就是人的位置和箱子的位置，因为总共8个状态值，而且横纵坐标的范围也不大，所以我们可以考虑一个8维的数组来存储状态。
代码如下：
#include<bits/stdc++.h> using namespace std; typedef unsigned int ui; typedef long long ll; typedef unsigned long long ull; #define pf printf #define mem(a,b) memset(a,b,sizeof(a)) #define prime1 1e9+7 #define prime2 1e9+9 #define pi 3.14159265 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define scand(x) scanf("%llf",&x) #define f(i,a,b) for(int i=a;i<=b;i++) #define scan(a) scanf("%d",&a) #define dbg(args) cout<<#args<<":"<<args<<endl; #define inf 0x3f3f3f3f #define maxn 10 int n,m,t; char Map[maxn][maxn]; bool vis[8][8][8][8][8][8][8][8]; int dir[][2]={0,1,0,-1,1,0,-1,0}; typedef struct{ int x,y; }point; struct node{ point h,v[3];//状态就是四个位置 int step; bool check()//检查目标状态是否达到 { f(i,0,2) { if(Map[v[i].x][v[i].y]!='@')return false;//只要有一个不在洞中就不是目标状态 } return true; } bool ok()//检测人所在的位置在初始地图中是否可行 { return h.x>=0&&h.x<n&&h.y>=0&&h.y<m&&Map[h.x][h.y]!='#'; } int judge()//判断人所在的位置有没有箱子,有则返回箱子的号码 { f(i,0,2) { if(h.x==v[i].x&&h.y==v[i].y) return i; } return -1; } }; node st; void setvis(node& a) { vis[a.h.x][a.h.y][a.v[0].x][a.v[0].y][a.v[1].x][a.v[1].y][a.v[2].x][a.v[2].y]=1; } bool getvis(node& a) { return vis[a.h.x][a.h.y][a.v[0].x][a.v[0].y][a.v[1].x][a.v[1].y][a.v[2].x][a.v[2].y]; } bool cango(node a,int num,int i)//箱子可以被推移一格 { a.v[num].x+=dir[i][0]; a.v[num].y+=dir[i][1]; if(a.v[num].x<0||a.v[num].x>=n||a.v[num].y<0||a.v[num].y>=m||Map[a.v[num].x][a.v[num].y]=='#')return false; f(j,0,2) { if(j==num)continue;//如果有其他箱子则不可行 if(a.v[j].x==a.v[num].x&&a.v[j].y==a.v[num].y)return false; } return true; } node cur,nxt; int bfs() { queue<node>q; q.push(st); setvis(st); int t; while(!q.empty()) { cur=q.front(); q.pop(); if(cur.check()) { return cur.step; } f(i,0,3) { nxt=cur; nxt.h.x+=dir[i][0];//人先移动 nxt.h.y+=dir[i][1]; nxt.step++; if(nxt.ok())//该位置可走 ，即在原地图中不是墙 { t=nxt.judge();//判断有没有箱子，有箱子的话就判断能不能推走 if(t==-1)//该位置上没有箱子又是可走的，说明此时是陆地 { if(!getvis(nxt)) { setvis(nxt); q.push(nxt); } } else { if(cango(nxt,t,i)) { nxt.v[t].x+=dir[i][0]; nxt.v[t].y+=dir[i][1]; if(!getvis(nxt)) { setvis(nxt); q.push(nxt); } } } } } } return -1; } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); std::ios::sync_with_stdio(false); while(scanf("%d%d",&n,&m)!=EOF) { int cnt=0; mem(vis,false); f(i,0,n-1) f(j,0,m-1) { scanf(" %c",&Map[i][j]); if(Map[i][j]=='X') { st.h.x=i,st.h.y=j; st.step=0; } if(Map[i][j]=='*') { st.v[cnt].x=i; st.v[cnt++].y=j; } } pf("%d ",bfs()); } }