P2324 [SCOI2005]骑士精神(A*)
2024-09-05 22:42:52
A*与爆搜的不同就是它有一个估价函数$h(x)$
这个估价函数一般设为从当前状态到终点状态的估计最短步数,这样可以有效剪枝
但估计值必须严格小于等于实际剩余步数,否则会剪枝过度而影响正确性
$g(x),f(x)$分别为剩余步数和已走步数,则:
$g(x)=f(x)+h(x)$
本题中的$h(x)$可以设为未归位的棋子数+1
因为每一步最多使一个棋子归位(除最后一步一次归位2个棋子)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int d1[]={,,,,-,-,-,-};
int d2[]={,-,,-,,-,,-};
char a[][]; int re,col[][];
inline bool is(int x,int y){return (x==&&y==)?(a[x][y]=='*'):(a[x][y]==col[x][y]+'');}
void dfs(int d,int s,int x,int y){//d当前步数,s已归位棋子个数
if(d+-s>=re||d>) return ;//f(x)=d,g(x)=24-s
if(s==) {re=min(re,d); return ;}
for(int i=;i<;++i){
int rx=x+d1[i],ry=y+d2[i],p=s;
if(rx<||<rx||ry<||<ry) continue;
p-=is(x,y)+is(rx,ry);
swap(a[x][y],a[rx][ry]);
p+=is(x,y)+is(rx,ry);
dfs(d+,p,rx,ry);
swap(a[x][y],a[rx][ry]);
}
}
int main(){
for(int i=;i<=;++i) for(int j=i;j<=;++j) col[i][j]=;
col[][]=col[][]=;
int T,sum,fx,fy;scanf("%d",&T);
while(T--){
sum=; re=;
for(int i=;i<=;++i){
scanf("%s",a[i]+);
for(int j=;j<=;++j){
sum+=is(i,j);
if(a[i][j]=='*') fx=i,fy=j;
}
}dfs(,sum,fx,fy);
if(re>) re=-;
printf("%d\n",re);
}return ;
}
最新文章
- 《HiWind企业快速开发框架实战》(3)使用HiWind创建和管理菜单
- Python语法二
- EMIF接口的寻址问题
- wso2esb简介
- poj1379 模拟退火
- java编程思想-java 异常使用指南
- C#生成条形码 Code128算法
- iOS UIApplicatin和它的delegate
- Unity UI和引用的管理中心
- putty修改编码
- 路由页面缓存开启 以及 keep-alive 给你埋下的坑
- 关于Hibernate
- 用UE4来做Zego即构的房间列表
- dubbo的架构
- C++实验1
- iOS中 Realm错误总结整理 韩俊强的博客
- Nigix配置
- JavaWeb基础—数据库连接池DBCP、C3P0
- linux计划任务 学习笔记
- bash 基础