https://www.luogu.org/problem/show?pid=P3930
这道题，其实完全不需要你去你用什么高级算法，其实需要你的，是耐心地爆搜，像2015年斗地主一样了，但有一个坑，我没注意到，于是得了80分，那就是：因为进攻方是骑士，所以进攻方是不可能吃到骑士的。大体呢就是先把开始点和结束点记录下来，然后开结构体，结构体里面要有它当时棋盘的状态和进攻方所在位置，然后把那些敌方的记录下来，每次往8个方向枚举，符合条件(就是没跳出棋盘，不会被地方吃到) 。因为宽搜要快一些，所以我们用宽搜，要开一个队列，搜到了第一个吃到国王的就跳出来，返回步数。搜完后还不行，就返回1.
注意：如果跳到了敌方的一个棋子上，就要把那颗棋子去掉！ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<cmath> using namespace std; const int inf=0x3f3f3f3f; struct wo{ char b[60][60];//棋盘状态 int x,y;// }; queue<wo>p; char a[60][60]; int vis[60][60];//记录有多少颗敌方棋子能吃到自己 int step[60][60];//记录到达当前点至少要用多少步 int n; int dx[8]={1,1,-1,-1,2,2,-2,-2};//八个方向 int dy[8]={2,-2,2,-2,1,-1,1,-1};//八个方向 int startx,starty,endx,endy;//开始点和结束点 int judge(int x,int y){ if(x<=0||x>n)return 0; if(y<=0||y>n)return 0; if(vis[x][y])return 0; return 1; } void queen(int x,int y){//皇后攻击范围内的 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if((i==x)||(j==y)||((i+j)==(x+y))||((i-j)==(x-y)))//横坐标一样，竖坐标一样，或者在同一条斜线上 vis[i][j]++;//能攻击到这一点 } } vis[x][y]--;//自己攻击不了自己！ } void castle(int x,int y){//城堡攻击范围 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if((i==x)||(j==y))//横坐标一样或竖坐标一样 vis[i][j]++;//能攻击到这一点 } } vis[x][y]--;//自己攻击不了自己！ } void B(int x,int y){//主教攻击范围 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(((i+j)==(x+y))||((i-j)==(x-y)))//在同一条斜线上 vis[i][j]++;//就吃得到 } } vis[x][y]--;//自己攻击不了自己！ } void knight(int x,int y){ for(int i=0;i<8;i++){ if(judge(x+dx[i],y+dy[i])){//在骑士的8个方向上，且在棋盘上 vis[x+dx[i]][y+dy[i]]++;//就吃得到 } } //因为攻击方也是骑士，所以攻击方吃不了 } void solider(int x,int y){ vis[x+1][y-1]++;vis[x+1][y+1]++;//士兵只能攻击到两个点 } void king(int x,int y){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(abs(x-i)<=1&&abs(y-j)<=1)vis[i][j]++;//国王的8个方向内能被吃到 } } vis[x][y]=0; //自己攻击不了自己！ } void me(int x,int y){ startx=x,starty=y;//记录开始坐标 } int solve(){ while(p.size())p.pop(); wo help; wo save; help.x=startx; help.y=starty; step[startx][starty]=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ help.b[i][j]=a[i][j]; } } for(int i1=1;i1<=n;i1++){ for(int j1=1;j1<=n;j1++){//一个一个地找敌方棋子，敌方棋子攻击范围内的就不能到 if(help.b[i1][j1]=='C')castle(i1,j1); else if(help.b[i1][j1]=='K')knight(i1,j1); else if(help.b[i1][j1]=='B')B(i1,j1); else if(help.b[i1][j1]=='Q')queen(i1,j1); else if(help.b[i1][j1]=='X')king(i1,j1); else if(help.b[i1][j1]=='P')solider(i1,j1); } }vis[endx][endy]=0;//毕竟吃到国王就赢了，不需考虑其它 if(judge(help.x,help.y)==0)return -1; p.push(help); while(p.size()){ help=p.front();p.pop(); if(step[endx][endy]!=inf){ return step[endx][endy]; } for(int i=0;i<8;i++){ memset(vis,0,sizeof(vis)); for(int i1=1;i1<=n;i1++){ for(int j1=1;j1<=n;j1++){//一个一个地找敌方棋子，敌方棋子攻击范围内的就不能到 if(help.b[i1][j1]=='C')castle(i1,j1); else if(help.b[i1][j1]=='K')knight(i1,j1); else if(help.b[i1][j1]=='B')B(i1,j1); else if(help.b[i1][j1]=='Q')queen(i1,j1); else if(help.b[i1][j1]=='X')king(i1,j1); else if(help.b[i1][j1]=='P')solider(i1,j1); } }vis[endx][endy]=0; if(judge(help.x+dx[i],help.y+dy[i])){//重点开始 ，如果跳到了棋盘上且不会被吃 if(step[help.x+dx[i]][help.y+dy[i]]>step[help.x][help.y]+1){//是走到当前点最优策略才行 step[help.x+dx[i]][help.y+dy[i]]=step[help.x][help.y]+1; save.x=help.x+dx[i];save.y=help.y+dy[i]; for(int ii=1;ii<=n;ii++){ for(int jj=1;jj<=n;jj++){ save.b[ii][jj]=help.b[ii][jj];//继承状态 } } save.b[save.x][save.y]='.';//把被“我”吃到的变成点 p.push(save); }//重点结束 } } } return -1; } int main() { while(scanf("%d",&n)!=EOF){ memset(step,inf,sizeof(step)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; if(a[i][j]=='O')me(i,j); if(a[i][j]=='X'){ endx=i,endy=j;//记录国王位置 } } } printf("%d\n",solve()); } return 0; }