压状态bfs
2024-08-26 20:11:34
一般地图很小，状态不多，可以装压或者hash，构造压缩或hash的函数，构造还原地图的函数，然后就无脑bfs(感觉就是SPFA)
题目：
1.玩具游戏：二进制压缩状态
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
int s,e;
bool vis[1<<17];
int dis[1<<17],map[5][5];
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
inline void div(int x){
for(int i=4;i>=1;--i){
for(int j=4;j>=1;--j){
map[i][j]=x&1;
x>>=1;
}
}
}
inline int zip(){
int x=0;
for(int i=1;i<=4;++i){
for(int j=1;j<=4;++j){
x<<=1;
x|=map[i][j];
}
}
return x;
}
inline void bfs(){
queue<int>q;
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
div(x);
for(int i=1;i<=4;++i){
for(int j=1;j<=4;++j){
if(map[i][j]!=1)continue;
for(int k=0;k<4;++k){
int xx=dx[k]+i;
int yy=dy[k]+j;
if(xx<1||xx>4||yy<1||yy>4)continue;
if(map[xx][yy])continue;
swap(map[xx][yy],map[i][j]);
int w=zip();
swap(map[xx][yy],map[i][j]);
if(dis[w]>dis[x]+1){
dis[w]=dis[x]+1;
if(!vis[w]){
q.push(w);
vis[w]=1;
}
}
}
}
}
}
}
int main(){
for(int i=1;i<=4;++i){
char t[10];
scanf("%s",t+1);
for(int j=1;j<=4;++j){
s<<=1;
if(t[j]=='1')s|=1;
}
}
for(int i=1;i<=4;++i){
char t[10];
scanf("%s",t+1);
for(int j=1;j<=4;++j){
e<<=1;
if(t[j]=='1')e|=1;
}
}
bfs();
cout<<dis[e]<<endl;
return 0;
}
2.八数码难题：偷懒 map来hash存状态，转移很少9!
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
using namespace std;
long long s,t;
int tot,dis[402880],m[4][4];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
map<long long ,int >h;
bool v[20],vis[400000];
inline long long poww(long long a,long long b){
long long ans=1;
while(b){
if(b&1)ans*=a;
a*=a;
b>>=1;
}
return ans;
}
inline void dfs(int pos,long long val){
if(pos>9){
h[val]=++tot;
return ;
}
for(int i=0;i<=8;++i){
if(v[i])continue;
v[i]=1;
dfs(pos+1,val+i*poww(10,pos-1));
v[i]=0;
}
}
inline void div(long long x){
for(int i=3;i>=1;--i){
for(int j=3;j>=1;--j){
m[i][j]=x%10;
x/=10;
}
}
}
inline long long zip(){
long long x=0;
for(int i=1;i<=3;++i){
for(int j=1;j<=3;++j){
x*=10;
x+=m[i][j];
}
}
return x+1000000000;
}
inline void bfs(){
queue<long long>q;
memset(dis,0x3f,sizeof(dis));
int ss=h[s];
vis[ss]=1;
dis[ss]=0;
q.push(s);
while(q.size()){
long long x=q.front();
q.pop();
vis[h[x]]=0;
div(x);
for(int i=1;i<=3;++i){
for(int j=1;j<=3;++j){
if(m[i][j])continue;
for(int k=0;k<4;++k){
int xx=dx[k]+i;
int yy=dy[k]+j;
if(xx<1||xx>3||yy<1||yy>3)continue;
if(!m[xx][yy])continue;
swap(m[xx][yy],m[i][j]);
long long temp=zip();
swap(m[xx][yy],m[i][j]);
int u=h[x];
int v=h[temp];
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
if(!vis[v]){
vis[v]=1;
q.push(temp);
}
}
}
}
}
}
}
int main(){
dfs(1,1000000000);
cin>>s;
s+=1000000000;
t=1123804765;
bfs();
cout<<dis[h[t]];
return 0;
}
最新文章
- Linux查看软件安装路径
- Hibernate 缓存机制
- Golang学习 - sort 包
- [JLOI2013]地形生成
- 今天，安装了一个GANGLIA玩玩，以后再测试NAGIOS吧。
- 【JAVA - SSM】之MyBatis输出映射
- Bzoj 1222: [HNOI2001]产品加工 动态规划
- 设置cell背景色半透明
- 浅谈spring——spring MVC（十一）
- Hybrid容器设计之第三方网站
- ArcGIS API for JavaScript 与 Vue.js
- OpenCV中OpenMP的使用
- mtu简单说明
- HTML中Meta标签中http-equiv属性
- SQLite3 C/C++ 开发接口简介
- Infopath 2010 接收SQL Server数据
- 6. go数组与冒泡排序
- ZOJ 3872 浙江2015年省赛试题
- maven 编译解决jdk 版本问题
- 使用HackRF和外部时钟实现GPS欺骗实验