本文共 1365 字，大约阅读时间需要 4 分钟。

立体推箱子

题目

解析

考虑设三个状态：

code:

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int dx[3][4]={
   {
   -1,0,2,0},{
   -1,0,1,0},{
   -2,0,1,0}},dy[3][4]={
   {
   0,2,0,-1},{
   0,1,0,-2},{
   0,1,0,-1}},dt[3][4]={
   {
   2,1,2,1},{
   1,0,1,0},{
   0,2,0,2}};int n,m,sx,sy,st,tx,ty,d[510][510][3];struct pa{
   int x,y,t;}o2,o3;bool v[510][510][3];char s[510][510];queue
       
        q;inline bool check(pa x){
   return x.x>=1&&x.x<=n&&x.y>=1&&x.y<=m&&s[x.x][x.y]!='#'&&(!v[x.x][x.y][x.t])&&(x.t?((x.t==1)?(1
        
         
          >s[i][j];if(s[i][j]=='O')tx=i,ty=j;else if(s[i][j]=='X')sx=i,sy=j,st=(s[i][j-1]=='X')?1:((s[i-1][j]=='X')?2:0);} memset(d,0,sizeof(d)),memset(v,0,sizeof(v)),q.push((pa){ sx,sy,st}),v[sx][sy][st]=1; while(q.size()) { o2=q.front(),q.pop(); if(o2.x==tx&&o2.y==ty&&!o2.t){ printf("%d\n",d[tx][ty][0]);while(q.size())q.pop();continue;} for(register int i=0;i<4;++i)if(check(o3=(pa){ o2.x+dx[o2.t][i],o2.y+dy[o2.t][i],dt[o2.t][i]}))d[o3.x][o3.y][o3.t]=d[o2.x][o2.y][o2.t]+1,v[o3.x][o3.y][o3.t]=1,q.push(o3); } if(!v[tx][ty][0])printf("Impossible\n"); } return 0;}
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/zhanglili1597895/article/details/118050911 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！