洛谷 P2324 [SCOI2005]骑士精神
程序员文章站
2022-05-03 22:17:44
[TOC] 题目 "戳" 思路 $dfs$。 $Code$ cpp include include include include include using namespace std; int t,mxd,map[6][6],b[6][6];//map存储现在骑士的分布,b是目标 int dx[ ......
目录
题目
思路
$dfs$。
$code$
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; int t,mxd,map[6][6],b[6][6];//map存储现在骑士的分布,b是目标 int dx[8]={-2,-2,-1,1,-1,1,2,2},dy[8]={-1,1,2, 2,-2,-2,-1,1};//顺序一定要讲究 void work(){ b[1][1]=1,b[1][2]=1,b[1][3]=1,b[1][4]=1,b[1][5]=1; b[2][1]=0,b[2][2]=1,b[2][3]=1,b[2][4]=1,b[2][5]=1; b[3][1]=0,b[3][2]=0,b[3][3]=-1,b[3][4]=1,b[3][5]=1; b[4][1]=0,b[4][2]=0,b[4][3]=0,b[4][4]=0,b[4][5]=1; b[5][1]=0,b[5][2]=0,b[5][3]=0,b[5][4]=0,b[5][5]=0; }//目标 inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; }//读优 bool bound(int x,int y){ if(x<=0||x>5||y<=0||y>5) return true;//越界 return false; } bool dfs(int step,int sum,int x,int y,int la){//x、y是空格的位置,step是当前步数 if(step+sum>mxd) return 0;//如果超过步数限制,直接返回0 if(sum==0) return 1;//全部归位,返回1 int qwqx,qwqy,p,temp; bool fl=0; for(int i=0;i<=7;++i){ if(i==(7-la)) continue;//这里可以体现出顺序的讲究 p=sum,qwqx=x+dx[i],qwqy=y+dy[i]; if(bound(qwqx,qwqy)) continue;//判断是否越界 /*这里仔细想一下还是能明白的*/ if(map[qwqx][qwqy]==b[qwqx][qwqy]&&map[qwqx][qwqy]!=b[x][y]) p++;//原来骑士归位了,改完没归位 if(map[qwqx][qwqy]!=b[qwqx][qwqy]&&map[qwqx][qwqy]==b[x][y]) p--;//原来骑士没归位,改完归位了 if(b[x][y]==-1) p++;if(b[qwqx][qwqy]==-1) p--;//原来空位归位了,改完没归位、原来空位没归位,改完归位了 temp=map[qwqx][qwqy],map[qwqx][qwqy]=map[x][y],map[x][y]=temp;//交换两个位置 fl=dfs(step+1,p,qwqx,qwqy,i);//继续搜 if(fl) return 1; temp=map[qwqx][qwqy],map[qwqx][qwqy]=map[x][y],map[x][y]=temp;//回溯 } return 0; } int main(){ work(); t=read(); char c; while(t--){ int x,y,mn=0; for(int i=1;i<=5;++i){ for(int j=1;j<=5;++j){ cin>>c; if(c=='*'){ map[i][j]=-1; x=i,y=j; } if(c=='1') map[i][j]=1; if(c=='0') map[i][j]=0; if(map[i][j]!=b[i][j]) mn++;//mn最后为最少需要几步就可以归位。 } } bool f=0; for(int i=mn;i<=16;++i){//枚举步数 mxd=i; if(dfs(0,mn,x,y,-1)){ f=1; printf("%d\n",i-1); break; } } if(!f) printf("-1\n"); } return 0; }