hdu1254推箱子 (BFS+BFS+状态压缩)

  
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

  
4
注意：同一个位置最多可以走8次。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
typedef struct nn
{int x,y;
}poit;
typedef struct nnn
{int man[2],xz[2];int step;
}node;
int map[10][10],n,m,dir[4][2]={0,-1,0,1,-1,0,1,0};
int locte(node a)//反回人和箱的相对位置
{if(a.man[0]==a.xz[0]){if(a.man[1]==a.xz[1]+1) return 1;//人在箱的右边if(a.man[1]==a.xz[1]-1) return 1<<1;//人在箱的左边}else if(a.man[1]==a.xz[1]){if(a.man[0]==a.xz[0]+1) return 1<<2;//人在箱的下方if(a.man[0]==a.xz[0]-1) return 1<<3;//人在箱的上方}return 0;
}
void bfs(int &ok,node a)//人移动，找出从人的位置可以到箱的四个方位，以ok来压缩可以推的位置
{poit p1,p2;queue<poit>q;int vist[10][10]={0};p1.x=a.man[0]; p1.y=a.man[1];//起点vist[p1.x][p1.y]=1;q.push(p1);while(!q.empty()){p1=q.front(); q.pop();for(int i=0;i<4;i++){p2.x=p1.x+dir[i][0]; p2.y=p1.y+dir[i][1];if(p2.x==a.xz[0]&&p2.y==a.xz[1])//箱的位置{a.man[0]=p1.x; a.man[1]=p1.y;ok|=locte(a);//压缩可到达的位置if(ok==15)return ;}else if(p2.x>=0&&p2.x<n&&p2.y>=0&&p2.y<m&&!vist[p2.x][p2.y]&&!map[p2.x][p2.y]){vist[p2.x][p2.y]=1; q.push(p2);}}}
}
int BFS(node a,poit end)//箱子移动
{int vist[10][10]={0},ok,x,y;queue<node>q;node b;vist[a.xz[0]][a.xz[1]]++; a.step=0;q.push(a);while(!q.empty()){a=q.front(); q.pop();ok=locte(a); bfs(ok,a);//找出可以推箱位置for(int i=0;i<4;i++)//向左推，右推，上推，下推 四个方向if(ok&(1<<i)){x=a.xz[0]+dir[i][0]; y=a.xz[1]+dir[i][1];if(x>=0&&x<n&&y>=0&&y<m&&vist[x][y]<9&&!map[x][y])//每个位置可以重复走，但最多走8次，每个方向2次{if(x==end.x&&y==end.y)//推到了指定的位置return a.step+1;b.man[0]=a.xz[0]; b.man[1]=a.xz[1];b.xz[0]=x; b.xz[1]=y; b.step=a.step+1;vist[x][y]++;//到达的次数加1q.push(b);}}}return -1;//不能推到指定位置
}
int main()
{int t;poit end;//指定要推到的位置node a;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf("%d",&map[i][j]);if(map[i][j]==4)a.man[0]=i,a.man[1]=j,map[i][j]=0;//记录下来后，清0else if(map[i][j]==2)a.xz[0]=i,a.xz[1]=j,map[i][j]=0;else if(map[i][j]==3)end.x=i,end.y=j,map[i][j]=0;}printf("%d\n",BFS(a,end));}
}