P1379 八数码难题
2024-08-25 21:31:46
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#include<vector>
using std::vector;
bool t[];
int a[][];
int ans=;
int tx[]={,,,-,};
int ty[]={,-,,,};
int pc[];
int zt=;
int erfen(int a)
{
int ans=-;
int l=,r=zt,mid=(l+r)/;
while(l<=r)
{
if(pc[mid]>a)
{
r=mid-;
mid=(l+r)/;
}
if(pc[mid]<a)
{
l=mid+;
mid=(l+r)/;
}
if(pc[mid]==a)
{
ans=mid;
return ans;
}
}
return ans;
}
void bfs(int x,int y,int a[][],int sum)
{ if(erfen(a[][]*+a[][]*+a[][]*
+a[][]*+a[][]*+a[][]*+a[][]*+a[][]*
+a[][])!=-) return ;//如果重复了,直接退出(删除节点)
if(a[][]*+a[][]*+a[][]*
+a[][]*+a[][]*+a[][]*+a[][]*+a[][]*
+a[][]==)
{
if(sum<ans) ans=sum;
cout<<"youyigejie"<<endl;
return ;
} //判断是否目标状态
sum++;
pc[++zt]=a[][]*+a[][]*+a[][]*
+a[][]*+a[][]*+a[][]*+a[][]*+a[][]*
+a[][];
sort(pc,pc++zt);
for(int i=;i<=;i++)
if(tx[i]+x>=&&tx[i]+x<=&&ty[i]+y>=&&ty[i]+y<=)
{
int t[][];
for(int i=;i<=;i++)
for(int j=;j<=;j++)
t[i][j]=a[i][j];
t[x][y]=t[tx[i]+x][ty[i]+y],t[tx[i]+x][ty[i]+y]=;
if(erfen(t[][]*+t[][]*+t[][]*
+t[][]*+t[][]*+t[][]*+t[][]*+t[][]*
+t[][])==-)bfs(x+tx[i],y+ty[i],t,sum); }
}
int main()
{ int x,y;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
cin>>a[i][j];
if(a[i][j]==) x=i,y=j;
}
bfs(x,y,a,);
cout<<ans<<endl;
return ;
}
最新文章
- 【实战Java高并发程序设计 4】数组也能无锁:AtomicIntegerArray
- Python 之路 Day5 - 常用模块学习
- 详解Android中AsyncTask的使用
- MySql增删改查命令
- [QDB] 幽灵分享:QDataSet+TQMSSQLConverter 实战技巧
- Emacs简易教程
- [OJ] Find Minimum in Rotated Sorted Array
- javascript数组去重算法-----4
- Ubuntu 15.04 安装rmagick 2.15.4
- BGP多线单IP技术实现形式以及其他双线对比
- 周一02.4变量&;垃圾回收机制
- Spring Boot – Jetty配置
- PHP内核深入研究 - 数组及其遍历顺序
- db2 varchar字段类型太大问题
- Spring中实现多数据源事务管理
- 个人git链接和git学习心得总结
- Red Hat OpenShift
- $(";#form1";). serialize()提交表单
- WASAPI、DirectSound/DS、WaveOut、Kernel Streaming/KS
- iOS - Core Animation(核心动画)