本文主要是介绍HDU 1254—— 推箱子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
宽搜
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define INF (1<<30)
struct Node
{int x,y;int step;int dir;Node(){}Node(int xx,int yy){x=xx;y=yy;}Node(int xx,int yy,int ss,int dd){x=xx;y=yy;step=ss;dir=dd;}
};
int n,m;
int map[10][10];
int vis[10][10][4];
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int bfsvis[10][10];
int judge(int x,int y)
{if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!=1)return 1;return 0;
}
int find(Node a,Node b,Node box)
{if(a.x==b.x&&a.y==b.y)return 1;queue<Node> q;memset(bfsvis,0,sizeof(bfsvis));bfsvis[a.x][a.y]=1;bfsvis[b.x][b.y]=2;q.push(a);q.push(b);while(!q.empty()){Node u=q.front();q.pop();for(int i=0;i<4;i++){int x=u.x+dir[i][0];int y=u.y+dir[i][1];if(judge(x,y)&&(x!=box.x||y!=box.y)){if(bfsvis[x][y]==0){bfsvis[x][y]=bfsvis[u.x][u.y];q.push(Node(x,y));}elseif(bfsvis[x][y]!=bfsvis[u.x][u.y])return 1;}} }return 0;
}
int bfs(Node start,Node end,Node now)
{queue<Node> q;memset(vis,0,sizeof(vis));for(int i=0;i<4;i++){int x=start.x+dir[i][0];int y=start.y+dir[i][1];if(judge(start.x+dir[(i+2)%4][0],start.y+dir[(i+2)%4][1])&&judge(x,y)&&find(Node(x,y),now,start)){vis[start.x][start.y][i]=1;q.push(Node(start.x+dir[(i+2)%4][0],start.y+dir[(i+2)%4][1],1,i));} }while(!q.empty()){Node u=q.front();q.pop();if(u.x==end.x&&u.y==end.y)return u.step;for(int i=0;i<4;i++){int x=u.x+dir[i][0];int y=u.y+dir[i][1];Node tmp(u.x+dir[u.dir][0],u.y+dir[u.dir][1]);if(judge(u.x+dir[(i+2)%4][0],u.y+dir[(i+2)%4][1])&&judge(x,y)&&vis[u.x][u.y][i]==0&&find(Node(x,y),tmp,u)){vis[u.x][u.y][i]=1;q.push(Node(u.x+dir[(i+2)%4][0],u.y+dir[(i+2)%4][1],u.step+1,i));}}}return -1;
}
int main()
{int t;cin>>t;while(t--){cin>>n>>m;Node start,end,now;for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf("%d",&map[i][j]);if(map[i][j]==2)start.x=i,start.y=j;if(map[i][j]==3)end.x=i,end.y=j;if(map[i][j]==4)now.x=i,now.y=j;}int ans=bfs(start,end,now);printf("%d\n",ans);}return 0;
}
/*
44
4 4
0 0 0 1
0 1 0 1
2 1 0 0
0 4 1 3*/这篇关于HDU 1254—— 推箱子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
