【BZOJ 1054】 [HAOI2008]移动玩具
移动 BZOJ 玩具
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
暴力题。 bfs 直接用二进制存储状态。(把二维变成一维 然后暴力从每个位置进行搜索就好 一共就2^16种状态。【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 5;
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
char s[N+10][N+10];
int a[N+10][N+10],dis[65599];
queue<int> dl;
int zh(int a[N+10][N+10]){
int temp = 1,cur = 0;
for (int i = 4;i >= 1;i--)
for (int j = 4;j >= 1;j--){
cur+=a[i][j]*temp;
temp*=2;
}
return cur;
}
int main(){
for (int i = 1;i <= 4;i++)
scanf("%s",s[i]+1);
for (int i = 1;i <= 4;i++)
for (int j = 1;j <= 4;j++)
a[i][j] = s[i][j]-'0';
int cs = zh(a);
dis[cs] = 1;
dl.push(cs);
for (int i = 1;i <= 4;i++)
scanf("%s",s[i]+1);
for (int i = 1;i <= 4;i++)
for (int j = 1;j <= 4;j++)
a[i][j] = s[i][j]-'0';
int goal = zh(a);
while (!dl.empty()){
int x = dl.front();
int step = dis[x];
dl.pop();
for (int i = 4;i >= 1;i--)
for (int j = 4;j >= 1;j--){
a[i][j] = x%2;
x/=2;
}
for (int i = 1;i <= 4;i++)
for (int j = 1;j <= 4;j++)
if (a[i][j]==1)
for (int k = 0;k < 4;k++)
{
int tx = i+dx[k],ty = j+dy[k];
if (tx<1 || tx>4 || ty<1 || ty>4) continue;
swap(a[tx][ty],a[i][j]);
int cur = zh(a);
if (dis[cur]==0){
dis[cur]=step+1;
dl.push(cur);
}
swap(a[tx][ty],a[i][j]);
}
}
printf("%d\n",dis[goal]-1);
return 0;
}
相关文章
- 干货 | 移动应用中使用OpenGL生成转场特效
- 【应急能力提升3】内网横向移动攻击模拟(上)
- TensorFlow 智能移动项目:11~12
- 移动前端头部标签(HTML5 head meta)详解编程语言
- SAP 移动类型详解编程语言
- [图]桌面端/移动端Vivaldi 3.8发布:阻止恼人的cookies弹窗
- 开发Vi Linux:移动开发技术革命(vilinux移动)
- 绑定 WiFi 和以太网,以使网络间移动更轻松
- 桌面/移动端 Ubuntu 将获重大 UI 升级
- 首份《移动支付时代的无人零售报告》发布:社交活跃度暗藏消费能力的密码
- 掌握Linux命令Move,快速移动文件和目录(linux命令move)
- SQL Server中简易移动表的实现(sqlserver移动表)
- 基于jquery的用鼠标画出可移动的div
- android实现关闭或开启移动网络数据