hdu1732 Pushbox bfs 细节比较多,需要注意
2024-10-08 22:59:13
题目链接: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());
}
}
最新文章
- Android——Toast.makeText()
- VC包含目录、附加依赖项、库目录及具体设置
- Swift-04-Designated&;&;Convenience
- css控制内容显示,自动加";...";
- 14_RHEL7安装mplayer
- java中完美打包
- 搭建环境Visual Studio 2013 社区版
- Sublime Text 3中配置运行Java
- discuz 更换域名 导致qq登录不能用的问题
- linux下tomcat无法访问问题(换一种说法:无法访问8080端口)
- 微信小程序弹出和隐藏遮罩层动画以及五星评分
- LeetCode算法题-Find Smallest Letter Greater Than Target(Java实现)
- Android中的Application类在应用程序中的应用
- 验证IP地址的有效性
- spring获取配制文件的参数
- 基础知识《零》---一张图读懂JDK,JRE,JVM的区别与联系
- 学JS必看-JavaScript数据结构深度剖析
- LeetCode--141--环形链表
- activiti自己定义流程之Spring整合activiti-modeler实例(一):环境搭建
- struct to point
热门文章
- Android APP性能及专项测试
- IPC thread写法太晦涩
- Windows下python3登陆和操作linux服务器
- 【C#】WechatPay-API-v3 使用平台证书加密内容与应答|通知验签(SHA256 with RSA)
- webpack配置中环境变量-process.env. NODE_ENV
- Swift--struct与class的区别(汇编角度底层分析)
- 优雅的创建一个JavaScript库
- 自己查与写的批量比较bash
- 解决Hexo博客模板hexo-theme-next的翻页按钮不正常显示问题
- 『配置』服务器搭建 Office Online Server2016 实现文档预览 番外 错误篇