C. 【例题3】立体推箱子

在这里插入图片描述

题解

求最少步数，当然用广搜。

队列里记录当前这一步的三个状态，分别是：坐标（x,y）和箱子状态（ t ）。

其中箱子的状态有三种：立着，横躺着，竖躺着。分别用0,1,2表示。

箱子横着躺或竖着躺占两个格子，对于横躺，将其坐标记作右边的格子；对于竖躺，坐标记作下面的格子。

再加些处理（程序注释里有解释）便可把这个复杂的游戏变成简单的广搜走迷宫了~

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int sx,sy,st,ex,ey,n,m,a[510][510],d[510][510][3];//dx,dy,dt记录x,y,t在不同状态下往不同方向走的变化int dx[3][4]={
   	{
   0,2,0,-1},	{
   0,1,0,-1},	{
   0,1,0,-2}};int dy[3][4]={
   	{
   2,0,-1,0},	{
   1,0,-2,0},	{
   1,0,-1,0}};int dt[3][4]={
   	{
   1,2,1,2},	{
   0,1,0,1},	{
   2,0,2,0}};bool f[510][510][3];struct node{
   	int x,y,t;};bool check(int x,int y,int t)//检查这一步走得符不符合规则{
   	if(x<1||y<1||x>n||y>m||a[x][y]=='#') return 0;	if(t==0&&a[x][y]=='E') return 0;	if(t==1&& (y-1<1||a[x][y-1]=='#')) return 0;	if(t==2&& (x-1<1||a[x-1][y]=='#')) return 0;	return 1;}void bfs(){
   	f[sx][sy][st]=1;	queue
        
          q; q.push(node { sx,sy,st}); do { node j=q.front(); int x=j.x,y=j.y,t=j.t; q.pop(); if(x==ex&&y==ey&&t==0)//找到答案就直接输出并退出 { cout<
         
          <
          
           >n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { a[i][j]=getchar(); //读入到有效信息为止 while(a[i][j]!='#'&&a[i][j]!='.'&&a[i][j]!='E'&&a[i][j]!='X'&&a[i][j]!='O') a[i][j]=getchar(); if(a[i][j]=='X')//处理起点信息 { sx=i; sy=j; if(a[i][j-1]=='X') st=1; if(a[i-1][j]=='X') st=2; } if(a[i][j]=='O') { ex=i; ey=j; } } }}bool work(){ in(); if(!n&&!m) return 0; bfs(); return 1;}int main(){ while((work())) { memset(f,0,sizeof(f)); memset(d,0,sizeof(d)); //初始化，因为有多测 }}