当前位置：首页 > news >正文

0x27 A* + 0x28 IDA*

news 2025/5/8 5:48:41

一、A*

AcWing 178. 第K短路

f（x）设计，到终点的最短路一定小于等于第k短路，取最短路即可

可转换为由终点至任意点在反图上的最短路

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> pll;
const long long N=1e3+5,M=2e4+5;
long long n,m,s,t,k,dist[N],bis[N],vis[N];
long long head[N],v[M],e[M],nxt[M],tot;
long long head2[N],v2[M],e2[M],nxt2[M],tot2;
void add1(long long a,long long b,long long c){nxt[++tot]=head[a];v[tot]=b,e[tot]=c;head[a]=tot;
}
void add2(long long a,long long b,long long c){nxt2[++tot2]=head2[a];v2[tot2]=b,e2[tot2]=c;head2[a]=tot2;
}
struct S{long long v,l,x;friend bool operator<(S a,S b){if(a.v!=b.v)return a.v>b.v;return a.l>b.l;}
};
priority_queue<pll,vector<pll>,greater<pll> >q1;
priority_queue<S>q;
void dij(){memset(dist,0x3f,sizeof(dist));q1.push({0,t});dist[t]=0;while(q1.size()){long long x=q1.top().second;q1.pop();if(bis[x])continue;bis[x]=1;for(long long i=head2[x];i;i=nxt2[i]){long long y=v2[i],z=e2[i];if(dist[y]>dist[x]+z){dist[y]=dist[x]+z;q1.push({dist[y],y});}}}
}
long long Astar(){vis[s]=-1;q.push({dist[s],0,s});while(!q.empty()){long long x=q.top().x,l=q.top().l;q.pop();if(vis[x]==k)continue;vis[x]++;if(vis[x]==k&&x==t){return l;}for(long long i=head[x];i;i=nxt[i]){long long y=v[i],z=e[i];if(vis[y]<k){q.push({dist[y]+l+z,l+z,y});}}}return -1;
}
int main(){scanf("%lld%lld",&n,&m);for(long long i=1;i<=m;i++){long long a,b,c;scanf("%lld%lld%lld",&a,&b,&c);add1(a,b,c);add2(b,a,c);}scanf("%lld%lld%lld",&s,&t,&k);dij();printf("%lld",Astar());return 0;
}

AcWing 179. 八数码

启发式搜索必须问题有解，先判定可解性，否则会变成无头苍蝇

这题的可见性判定可参照

0x05排序

因为一次只能使一个方格的横坐标变化，f(x)取当前状态与目标状态各个数字的曼哈顿距离之和即可

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int a,b,c[10],tot; 
int d[]={-1,1,3,-3};
int fd=-1;
int rx[]={0,0,0,1,1,1,2,2};
int ry[]={0,1,2,0,1,2,0,1};
struct S{string s,la;int v,st,f;friend bool operator<(S a,S b){return a.v>b.v;}
};
priority_queue<S>q;
char op;
string ans;
string st,ed="12345678x";unordered_map<string,pair<int,string> >mp;
int H(string s){int ans=0;for(int i=0;i<9;i++){int x=i/3,y=i%3;if(s[i]!='x'){ans+=abs(x-rx[s[i]-'1'])+abs(y-ry[s[i]-'1']);}}return ans;
}
void print(){string now=ed;while(now!=st){if(mp[now].first==0){ans+='r';}if(mp[now].first==1){ans+='l';}if(mp[now].first==2){ans+='u';}if(mp[now].first==3){ans+='d';}now=mp[now].second;}
}
int main(){fd=-1;for(int i=0;i<3;i++){for(int j=0;j<3;j++){cin>>op;if(op=='x'){}else{c[++tot]=op-'0';}st+=op;}}for(int i=1;i<=8;i++){for(int j=i+1;j<=8;j++){if(c[j]<c[i]){b++;}} }if(b%2!=0){printf("unsolvable");return 0;}q.push({st,"",H(st),0,0});while(!q.empty()){string s=q.top().s,ss=q.top().s,la=q.top().la;int st=q.top().st,f=q.top().f;q.pop();if(mp.find(s)!=mp.end())continue;mp[s].first=f;mp[s].second=la;if(s==ed){fd=st;break;}for(int i=0;i<9;i++){for(int j=0;j<4;j++){if(j==0&&i%3==0)continue;if(j==1&&i%3==2)continue;int ii=i+d[j];if(ii>=0&&ii<=8&&s[ii]=='x'){swap(s[ii],s[i]);q.push({s,ss,H(s)+st+1,st+1,j});swap(s[ii],s[i]);}}}}if(fd==-1){printf("unsolvable");return 0;}print();for(int i=ans.size()-1;i>=0;i--){cout<<ans[i];}return 0;
}

这里采取字符串hash

Wing 193. 算乘方的牛

f(x)大数乘多少次二能变为x

注意：若大数超过x，除一次也能变为x，代价最小为零，且与小数没关系

#include<bits/stdc++.h>
using namespace std;
int p;
int gcd(int x,int y){if(y==0)return x;return gcd(y,x%y);
}
map<pair<short,short>,bool>mp;int h(int a){int res=0;for(int i=a;i<p;i*=2) res++;return res;
}
struct S{int a,b,st,v;friend bool operator<(S a,S b){return a.v>b.v;}
};
priority_queue<S>q;
void ins(int a,int b,int st){if(a<b)swap(a,b);if(p%(max(1,gcd(a,b)))!=0)return ;if(a==0)return ;q.push({a,b,st,st+h(a)});
}int main(){scanf("%d",&p);ins(1,0,0);while(!q.empty()){int a=q.top().a,b=q.top().b,st=q.top().st;q.pop();if(a==p||b==p){printf("%d",st);return 0;}if(mp[{a,b}])continue;mp[{a,b}]=1;ins(a,a*2,st+1);ins(b,b*2,st+1);ins(b,a*2,st+1);ins(a,b*2,st+1);ins(a,a+b,st+1);ins(b,a+b,st+1);ins(a,abs(a-b),st+1);ins(b,abs(a-b),st+1);}return 0;
}

二、IDA*

AcWing 180. 排书

一次改变最多三个后缀，f(x)改为错误后缀数除以三向上取整即可

千万别用vector，会T~~（别猜我怎么知道的）~~

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n,lim,fd;
int a[20];
unordered_map<ull,bool>mp;
ull h(){ull res;for(int i=1;i<=n;i++){res=res*1331+a[i];}return res;
}
int tot;
inline int f(){int tot=0;for(int i=1;i<n;i++){tot+=(a[i + 1] != a[i] + 1);}return (tot+2)/3;
} 
inline bool check(){for(int i=1;i<=n;i++){if(a[i]!=i)return 0;}return 1;
}
inline void d(int x,int y,int z,int *v){int tot=0;for(int i=1;i<=z;i++){if(i<x||i>y)v[++tot]=a[i];}for(int i=x;i<=y;i++){v[++tot]=a[i];}for(int i=z+1;i<=n;i++){if(i<x||i>y)v[++tot]=a[i];}for(int i=1;i<=n;i++){a[i]=v[i];} 
}
inline void r(int* v){for(int i=1;i<=n;i++){v[i]=a[i];} 
}
inline void w(int* v){for(int i=1;i<=n;i++){a[i]=v[i];} 
}
void dfs(int x){if(fd)return ;if(f()+x>lim+1)return;mp[h()]=1;if(check()){fd=1;return ;}int id;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){for(int k=0;k<=n;k++){int v[16],tmp[16];r(tmp);d(i,j,k,v);dfs(x+1);w(tmp);}}}
}
int main(){int T;cin>>T;while(T--){scanf("%d",&n);fd=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=0;i<=4;i++){lim=i;tot=0;dfs(1);if(fd){printf("%d\n",i);break;}}if(!fd){printf("5 or more\n");}}return 0;
}

AcWing 181. 回转游戏

转一次只能最多多一个某数，f(x)取除了中间最多的数外的数个数

#include<bits/stdc++.h>
using namespace std;
int a[4][8]={{1,3,7,12,16,21,23},{2,4,9,13,18,22,24},{5,6,7,8,9,10,11},{14,15,16,17,18,19,20}};
int ed[8]={7,8,9,12,13,16,17,18};
int p[30];
int lim,fd;inline bool check(){for(int i=1;i<8;i++){if(p[ed[i]]!=p[ed[i-1]])return 0;}return 1;
}
inline int f(){int t[4]={0},ans=0;for(int i=0;i<8;i++){t[p[ed[i]]]++;}ans=max(ans,t[1]);ans=max(ans,t[2]);ans=max(ans,t[3]);return 8-ans;
}
inline void le(int n){int x=p[a[n][0]];for(int i=1;i<7;i++){swap(p[a[n][i]],p[a[n][i-1]]);}p[a[n][6]]=x;
}
inline void ri(int n){int x=p[a[n][6]];for(int i=6;i>=0;i--){swap(p[a[n][i]],p[a[n][i+1]]);}p[a[n][0]]=x;
}
void dfs(int x,string s){if(fd)return ;if(x-1+f()>lim)return ;if(check()){cout<<s<<"\n"<<p[ed[0]]<<"\n";fd=1;return;}if(s[s.size()-1]!='F'){le(0);dfs(x+1,s+'A');ri(0);}if(s[s.size()-1]!='E'){le(1);dfs(x+1,s+'B');ri(1);}if(s[s.size()-1]!='H'){ri(2);dfs(x+1,s+'C');le(2);}if(s[s.size()-1]!='G'){ri(3);dfs(x+1,s+'D');le(3);}if(s[s.size()-1]!='B'){ri(1);dfs(x+1,s+'E');le(1);}if(s[s.size()-1]!='A'){ri(0);dfs(x+1,s+'F');le(0);}if(s[s.size()-1]!='D'){le(3);dfs(x+1,s+'G');ri(3);}if(s[s.size()-1]!='C'){le(2);dfs(x+1,s+'H');ri(2);}
}
int main(){while(~scanf("%d",&p[1])){if(p[1]==0){break;}for(int i=2;i<=24;i++){scanf("%d",&p[i]);}if(check()){printf("No moves needed\n");printf("%d\n",p[ed[0]]);continue;}for(int i=1;i<=100;i++){fd=0;lim=i;dfs(1,"");if(fd)break;}}return 0;
}

AcWing 182. 破坏正方形

f（x）取把正方形的四边全删去的删的次数显然没问题

这道题处理很麻烦，需注意

因为破坏小的很容易影响大的，所以正方形按从小到大排序

#include<bits/stdc++.h>
using namespace std;
int T,tot,t,n,m,lim,fd;  
int v[61][21],num[61];
bool u[61];
int calcc(int x,int y){return (2*n+1)*x+y+1;
}
int calcr(int x,int y){return (2*n+1)*x+y+1+n;
}inline int f(){int res=0;static bool tmp[61];memcpy(tmp,u,sizeof(u));for(int i=1;i<=m;i++)tmp[i]=u[i];for(int i=1;i<=tot;i++){int f=1;for(int j=1;j<=num[i];j++){if(!tmp[v[i][j]]){f=0;break;}}if(f){res++;for(int j=1;j<=num[i];j++){tmp[v[i][j]]=0;}}}return res;
}
void print(){for(int i=1;i<=m;i++){printf("%d ",u[i]);} puts("");
}void dfs(int x){if(fd)return ;if(f()>x){return ;}for(int i=1;i<=tot;i++){int f=1;for(int j=1;j<=num[i];j++){if(!u[v[i][j]]){f=0;break;}}if(f){for(int j=1;j<=num[i];j++){u[v[i][j]]=0;dfs(x-1);u[v[i][j]]=1;}return;}}fd=1;
}                                                                                         
int main(){cin>>T;while(T--){int nn=n;cin>>n;tot=0;memset(num,0,sizeof(num));memset(v,0,sizeof(v));for(int k=1;k<=n;k++){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(i+k>n||j+k>n)continue;tot++;for(int y=j;y<=j+k-1;y++){v[tot][++num[tot]]=calcc(i,y);}for(int x=i;x<=i+k-1;x++){v[tot][++num[tot]]=calcr(x,j);}for(int x=i;x<=i+k-1;x++){v[tot][++num[tot]]=calcr(x,j+k);}for(int y=j;y<=j+k-1;y++){v[tot][++num[tot]]=calcc(i+k,y);}}}}m=calcc(n,n-1);for(int i=1;i<=m;i++){u[i]=1;}scanf("%d",&t);for(int i=1;i<=t;i++){int x;scanf("%d",&x);u[x]=0;}for(int i=0;i<=100;i++){fd=0;dfs(i);if(fd){printf("%d\n",i);break;}}}return 0;
}

AcWing 194. 涂满它！

f(x)设计，在联通块以外的颜色个数

这题处理不要傻傻广搜，标记那些点被访问过了，找相邻点flood-fill

#include<bits/stdc++.h>
using namespace std;
int n,a[10][10],lim,fd,s[10][10];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};void print(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){printf("%d",s[i][j]);}puts("");}
}int f(){int vis[6]={}; for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(s[i][j]==0)vis[a[i][j]]=1;}}return max(0,vis[0]+vis[1]+vis[2]+vis[3]+vis[4]+vis[5]-1);
}bool check(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(!s[i][j]){return 0;}}}return 1;
}
void flood(int x,int y){s[x][y]=1;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx<=0||xx>n||yy<=0||yy>n||s[xx][yy])continue;if(a[xx][yy]==a[x][y]){flood(xx,yy);}}
}
void dfs(int x){//printf("%d\n",x);print();puts("");if(fd){return ;}if(x-1+f()>lim){return ;}if(check()){fd=1;return ;}int k[10][10];memcpy(k,s,sizeof(k));for(int d=0;d<=5;d++){int f=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(s[i][j]||a[i][j]!=d)continue;for(int dd=0;dd<4;dd++){int xx=i+dx[dd],yy=j+dy[dd];if(xx<=0||xx>n||yy<=0||yy>n||s[xx][yy]==0)continue;flood(i,j);f=1;break;} }}if(f)dfs(x+1);memcpy(s,k,sizeof(k));}
}int main(){while(~scanf("%d",&n)&&n){memset(s,0,sizeof(s));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&a[i][j]);}}flood(1,1);for(int i=0;i<=100;i++){lim=i;fd=0;dfs(1);if(fd){printf("%d\n",i);break;}}}return 0;
}

AcWing 195. 骑士精神

最简单的题了，f（x）取不对的棋子数即可

#include<bits/stdc++.h>
using namespace std;
int T,lim,fd;
char s[7][7];
int a[6][6],stx,sty,ed[6][6]={{0,0,0,0,0,0},{0,1,1,1,1,1},{0,0,1,1,1,1},{0,0,0,2,1,1}, {0,0,0,0,0,1},{0,0,0,0,0,0}};
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,-1,1,-1,1};
void print(){for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){printf("%d",a[i][j]);}puts("");}
}
int f(){int res=0;for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){if(i!=3||j!=3){if(a[i][j]!=ed[i][j]){res++;}}}}return res;
}
bool check(){for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){if(a[i][j]!=ed[i][j])return 0;}}return 1;
}
void dfs(int x,int bx,int by){//print();puts("");//printf("%d %d:%d %d\n",x,f(),bx,by);if(fd)return ;if(x-1+f()>lim)return ;if(check()){fd=1;return;}for(int d=0;d<8;d++){int xx=bx+dx[d],yy=by+dy[d];if(xx<1||xx>5||yy<1||yy>5)continue;swap(a[xx][yy],a[bx][by]);dfs(x+1,xx,yy);swap(a[xx][yy],a[bx][by]);}
}
int main(){scanf("%d",&T);while(T--){for(int i=1;i<=5;i++){scanf("%s",s[i]+1);    }for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){if(s[i][j]=='0'){a[i][j]=0;}else if(s[i][j]=='1'){a[i][j]=1;}else{a[i][j]=2;stx=i,sty=j;}}}for(int i=0;i<=15;i++){fd=0;lim=i;dfs(1,stx,sty);if(fd==1){printf("%d\n",i);break;}}if(!fd)printf("-1\n");}return 0;
}