题目链接: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[][][][][][][][];
int dir[][]={,,,-,,,-,};
typedef struct{
int x,y;
}point;
struct node{
point h,v[];//状态就是四个位置
int step;
bool check()//检查目标状态是否达到
{
f(i,,)
{
if(Map[v[i].x][v[i].y]!='@')return false;//只要有一个不在洞中就不是目标状态
}
return true;
}
bool ok()//检测人所在的位置在初始地图中是否可行
{
return h.x>=&&h.x<n&&h.y>=&&h.y<m&&Map[h.x][h.y]!='#';
}
int judge()//判断人所在的位置有没有箱子,有则返回箱子的号码
{
f(i,,)
{
if(h.x==v[i].x&&h.y==v[i].y)
return i;
}
return -;
}
};
node st;
void setvis(node& a)
{
vis[a.h.x][a.h.y][a.v[].x][a.v[].y][a.v[].x][a.v[].y][a.v[].x][a.v[].y]=;
}
bool getvis(node& a)
{
return vis[a.h.x][a.h.y][a.v[].x][a.v[].y][a.v[].x][a.v[].y][a.v[].x][a.v[].y];
}
bool cango(node a,int num,int i)//箱子可以被推移一格
{
a.v[num].x+=dir[i][];
a.v[num].y+=dir[i][];
if(a.v[num].x<||a.v[num].x>=n||a.v[num].y<||a.v[num].y>=m||Map[a.v[num].x][a.v[num].y]=='#')return false;
f(j,,)
{
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,,)
{
nxt=cur;
nxt.h.x+=dir[i][];//人先移动
nxt.h.y+=dir[i][];
nxt.step++;
if(nxt.ok())//该位置可走 ,即在原地图中不是墙
{
t=nxt.judge();//判断有没有箱子,有箱子的话就判断能不能推走
if(t==-)//该位置上没有箱子又是可走的,说明此时是陆地
{
if(!getvis(nxt))
{
setvis(nxt);
q.push(nxt);
}
}
else
{
if(cango(nxt,t,i))
{
nxt.v[t].x+=dir[i][];
nxt.v[t].y+=dir[i][];
if(!getvis(nxt))
{
setvis(nxt);
q.push(nxt);
}
}
}
}
}
}
return -;
}
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=;
mem(vis,false);
f(i,,n-)
f(j,,m-)
{
scanf(" %c",&Map[i][j]);
if(Map[i][j]=='X')
{
st.h.x=i,st.h.y=j;
st.step=;
}
if(Map[i][j]=='*')
{
st.v[cnt].x=i;
st.v[cnt++].y=j;
}
}
pf("%d\n",bfs());
}
}

最新文章

  1. Android——Toast.makeText()
  2. VC包含目录、附加依赖项、库目录及具体设置
  3. Swift-04-Designated&amp;&amp;Convenience
  4. css控制内容显示,自动加&quot;...&quot;
  5. 14_RHEL7安装mplayer
  6. java中完美打包
  7. 搭建环境Visual Studio 2013 社区版
  8. Sublime Text 3中配置运行Java
  9. discuz 更换域名 导致qq登录不能用的问题
  10. linux下tomcat无法访问问题(换一种说法:无法访问8080端口)
  11. 微信小程序弹出和隐藏遮罩层动画以及五星评分
  12. LeetCode算法题-Find Smallest Letter Greater Than Target(Java实现)
  13. Android中的Application类在应用程序中的应用
  14. 验证IP地址的有效性
  15. spring获取配制文件的参数
  16. 基础知识《零》---一张图读懂JDK,JRE,JVM的区别与联系
  17. 学JS必看-JavaScript数据结构深度剖析
  18. LeetCode--141--环形链表
  19. activiti自己定义流程之Spring整合activiti-modeler实例(一):环境搭建
  20. struct to point

热门文章

  1. Android APP性能及专项测试
  2. IPC thread写法太晦涩
  3. Windows下python3登陆和操作linux服务器
  4. 【C#】WechatPay-API-v3 使用平台证书加密内容与应答|通知验签(SHA256 with RSA)
  5. webpack配置中环境变量-process.env. NODE_ENV
  6. Swift--struct与class的区别(汇编角度底层分析)
  7. 优雅的创建一个JavaScript库
  8. 自己查与写的批量比较bash
  9. 解决Hexo博客模板hexo-theme-next的翻页按钮不正常显示问题
  10. 『配置』服务器搭建 Office Online Server2016 实现文档预览 番外 错误篇