社区讨论
请问这里估价函数必须这样设置吗
P2324[SCOI2005] 骑士精神参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo164mor
- 此快照首次捕获于
- 2023/10/22 15:49 2 年前
- 此快照最后确认于
- 2023/11/02 15:24 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
char ed[5][5]={
{'1','1','1','1','1'},
{'0','1','1','1','1'},
{'0','0','*','1','1'},
{'0','0','0','0','1'},
{'0','0','0','0','0'}
},a[5][5];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
int dep,x,y;
int gj()
{
int ans=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
{
if(a[i][j]=='*'){
x=i;
y=j;
}
if(a[i][j]!=ed[i][j]) ++ans;
}
return ans;
}
bool dfs(int now)
{
int cnt=gj(),nowx=x,nowy=y;
if(now+cnt-1>dep) return 0;
if(!cnt) return 1;
for(int i=0;i<8;i++)
{
int nx=nowx+dx[i],ny=nowy+dy[i];
if(nx<0||nx>4||ny<0||ny>4) continue;
swap(a[nowx][nowy],a[nx][ny]);
if(dfs(now+1)) return 1;
swap(a[nowx][nowy],a[nx][ny]);
}
return 0;
}
signed main()
{
std::ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--)
{
for(int i=0;i<5;i++) cin>>a[i];
dep=0;
while(dep<=15&&!dfs(0)) ++dep;
if(dep==16) cout<<-1<<'\n';
else cout<<dep<<'\n';
}
}
摘自xht37巨佬为蓝书编写的标程. 请问估价函数设计的原则是什么?必须准确吗?这两个问题求教,谢谢!
回复
共 3 条回复,欢迎继续交流。
正在加载回复...