首页 > 代码库 > bzoj1085 [SCOI2005]骑士精神
bzoj1085 [SCOI2005]骑士精神
IDA*裸题,其实就是dfs加个最优性减枝。
#include<cstdio> inline void swap(int &x,int &y){int t=x; x=y; y=t;} const int map[5][5]={ 1,1,1,1,1, 0,1,1,1,1, 0,0,2,1,1, 0,0,0,0,1, 0,0,0,0,0 }; const int xx[8]={1,1,-1,-1,2,2,-2,-2}; const int yy[8]={2,-2,2,-2,1,-1,1,-1}; int yes=0,a[5][5],b[5][5]; void search(int tot,int to,int x,int y,int num){ if(tot==to){if(!num) yes=1; return;} for(int i=0;i<8;i+=1){ if(yes) return; int tox=x+xx[i],toy=y+yy[i]; int t=num; if(tox<0 || tox>4 || toy<0 || toy>4) continue; if(a[x][y]==map[x][y]) num+=1; if(a[tox][toy]==map[tox][toy]) num+=1; swap(a[x][y],a[tox][toy]); if(a[x][y]==map[x][y]) num-=1; if(a[tox][toy]==map[tox][toy]) num-=1; if(num+tot<=to) search(tot+1,to,tox,toy,num); swap(a[x][y],a[tox][toy]); num=t; } } int main(){ int T,x,y; for(scanf("%d",&T);T;T-=1){ for(int i=0;i<5;i+=1) for(int j=0;j<5;j+=1){ char c; while(c=getchar(),(c<‘0‘ || c>‘1‘) && c!=‘*‘); if(c!=‘*‘)a[i][j]=c-‘0‘; else {a[i][j]=2; x=i;y=j;} } int num=0; for(int i=0;i<5;i+=1) for(int j=0;j<5;j+=1) if(a[i][j]!=map[i][j]) num++; for(int i=num-1;i<=15;i+=1){ search(0,i,x,y,num); if(yes){printf("%d\n",i); break;} } yes?yes=0:printf("-1\n"); } return 0; }
bzoj1085 [SCOI2005]骑士精神
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。