萌新求助A*
- 板块P1379 八数码难题
- 楼主Justin999
- 当前回复5
- 已保存回复5
- 发布时间2022/8/23 12:38
- 上次更新2023/10/27 14:02:57
查看原帖
被骇客银狼阻止的越权访问保存失败
萌新求助A*
A*97pts代码,wa在#12：
// Problem: P1379 八数码难题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1379
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
int t[3][3]={{1,2,3},{8,0,4},{7,6,5}};
const int go[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct Node{
int step;
int st[3][3];
int GetF()const{
int h=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
h+=(st[i][j]!=t[i][j]);
return step;
}
pair<int,int> GetZero()const{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(!st[i][j])
return make_pair(i,j);
return make_pair(-1,-1);
}
int GetVal()const{
int res=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
res=res*10+st[i][j];
return res;
}
void print()const{
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)
printf("%d ",st[i][j]);
putchar('\n');
}
}
}s;
bool operator<(const Node& x,const Node& y){return x.GetF()<y.GetF();}
bool operator>(const Node& x,const Node& y){return x.GetF()>y.GetF();}
priority_queue<Node,vector<Node>,greater<Node>> heap;
set<int> ck;
int AStar(){
Node top,tmp;
heap.push(s);
ck.emplace(s.GetVal());
while(!heap.empty()){
top=heap.top();
// top.print();
// for(int i=0;i<3;i++){
// for(int j=0;j<3;j++)
// printf("%d ",t[i][j]);
// putchar('\n');
// }
if(memcmp(top.st,t,sizeof(t))==0) return top.step;
heap.pop();
pair<int,int> p=top.GetZero();
int x0=p.first,y0=p.second;
for(int i=0;i<4;i++){
int newx=x0+go[i][0],newy=y0+go[i][1];
if(newx>=3||newx<0||newy>=3||newy<0) continue;
tmp=top;
tmp.step++,swap(tmp.st[x0][y0],tmp.st[newx][newy]);
if(ck.count(tmp.GetVal())) continue;
ck.emplace(tmp.GetVal());
heap.push(tmp);
}
}
}
int main(){
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
s.st[i][j]=getchar()-'0';
s.step=0;
printf("%d\n",AStar());
return 0;
}
稍微调整估价函数后(其实就是改成BFS)AC了:
// Problem: P1379 八数码难题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1379
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
int t[3][3]={{1,2,3},{8,0,4},{7,6,5}};
const int go[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct Node{
int step;
int st[3][3];
int GetF()const{
int h=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
h+=(st[i][j]!=t[i][j]);
return step;
}
pair<int,int> GetZero()const{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(!st[i][j])
return make_pair(i,j);
return make_pair(-1,-1);
}
int GetVal()const{
int res=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
res=res*10+st[i][j];
return res;
}
void print()const{
for(int i=0;i<3;i++){
for(int j=0;j<3;j++)
printf("%d ",st[i][j]);
putchar('\n');
}
}
}s;
bool operator<(const Node& x,const Node& y){return x.GetF()<y.GetF();}
bool operator>(const Node& x,const Node& y){return x.GetF()>y.GetF();}
priority_queue<Node,vector<Node>,greater<Node>> heap;
set<int> ck;
int AStar(){
Node top,tmp;
heap.push(s);
ck.emplace(s.GetVal());
while(!heap.empty()){
top=heap.top();
// top.print();
// for(int i=0;i<3;i++){
// for(int j=0;j<3;j++)
// printf("%d ",t[i][j]);
// putchar('\n');
// }
if(memcmp(top.st,t,sizeof(t))==0) return top.step;
heap.pop();
pair<int,int> p=top.GetZero();
int x0=p.first,y0=p.second;
for(int i=0;i<4;i++){
int newx=x0+go[i][0],newy=y0+go[i][1];
if(newx>=3||newx<0||newy>=3||newy<0) continue;
tmp=top;
tmp.step++,swap(tmp.st[x0][y0],tmp.st[newx][newy]);
if(ck.count(tmp.GetVal())) continue;
ck.emplace(tmp.GetVal());
heap.push(tmp);
}
}
}
int main(){
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
s.st[i][j]=getchar()-'0';
s.step=0;
printf("%d\n",AStar());
return 0;
}
为什么A*出了问题啊
加载中...