P3930 一道大水题 Knight 题解
T_TLucas_Yin · · 题解
加上多组数据后一遍就过了并最优解第五很高兴，写一篇题解。
本题解优点在于较详细的搜索步骤解释。
每组数据的核心思路：
- 对数据进行初始化，输入棋盘，记下起点（
O）和终点（X）的位置。 - 采用广搜。建立优先队列，将起点入队。
- 取出队首节点（出队）。
- 判断如果是终点，则输出当前的步数并直接结束该组数据。
- 判断如果有未吃掉的敌方棋子能吃掉该格的马，则回到第三步。
- 判断如果该格有敌方棋子，则标记该棋子为被吃掉状态。
- 遍历马的方向数组，把该节点能通向的未走过节点全部入队。（很板子的广搜思想）
- 回到第三步。
其中最难写的部分其实是“判断有没有未吃掉的敌方棋子能吃掉该格的马”。该步骤的方法是遍历敌方的所有棋子，看白马是否在它们的攻击范围内。如果白马在其中任何一枚棋子的攻击范围内，它就会失败。
接下来说说每一种棋子分别应该怎么判断。
城堡（车）
如果白马与车在同一行，则沿列从车开始先后向两侧遍历。如果任意方向碰到了白马，则返回白马被吃掉。如果遇到了其他敌方棋子，则视为攻击被打断，跳出循环。
如果白马与车在同一列，则沿行遍历，其余同上。
骑士（马）
借用广搜使用的马的方向数组。如果黑马往任何一个方向跳时碰到了白马，则返回白马被吃掉。
主教（象）
依次遍历四个方向：行列坐标同时减；行坐标减且列坐标加；行坐标加且列坐标减；行列坐标同时加。如果一个方向上碰到了白马，则返回白马被吃掉。如果碰到了其他黑子，则跳出该方向。
皇后（后）
先按照车的方式判断，再紧接着按照象的方式判断。是的，没什么好改的。
国王（王）
为它单独开一个
士兵（兵）
直接判断它下一行左一列、下一行右一列两个方向上是否碰到了白马即可。
以上本题的难点就结束了。其实写起来代码只是看着长，并没有很难。
代码中也有必要的注释。
#include<bits/stdc++.h>
using namespace std;
int n,top,sx,sy,ex,ey;
struct node{
bool flag[65];//每一个敌方棋子是否被吃掉了
int x,y,k;//坐标，步数
bool operator <(const node &b) const{
return k>b.k;
}
}a;
struct chess{
char c;
int x,y;
}f[65];
map<pair<int,int>,int> ma;
char c[65][65];
bool fl[65][65];
priority_queue<node> q;
int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
bool in(int x,int y){
if(x<1||x>n) return 0;
if(y<1||y>n) return 0;
return 1;
}
bool check(node t){
int sx=t.x,sy=t.y;
for(int i=1;i<=top;i++){//遍历所有棋子
if(t.flag[i]) continue;
if(f[i].c=='C'){//车
int x=f[i].x,y=f[i].y;
if(x==sx){
for(int j=y-1;j>=1;j--){//在左边
if(j==sy) return 1;
if(ma.count({x,j})&&!t.flag[ma[{x,j}]]) break;//遇到别的棋子就打断攻击范围
}
for(int j=y+1;j<=n;j++){//在右边
if(j==sy) return 1;
if(ma.count({x,j})&&!t.flag[ma[{x,j}]]) break;
}
}
if(y==sy){
for(int j=x-1;j>=1;j--){//在上边
if(j==sx) return 1;
if(ma.count({j,y})&&!t.flag[ma[{j,y}]]) break;
}
for(int j=x+1;j<=n;j++){//在下边
if(j==sx) return 1;
if(ma.count({j,y})&&!t.flag[ma[{j,y}]]) break;
}
}
}
else if(f[i].c=='K'){//马
int x=f[i].x,y=f[i].y;
for(int j=0;j<8;j++){//8个方向，找到了就能杀
int xx=x+dx[j],yy=y+dy[j];
if(in(xx,yy)&&sx==xx&&sy==yy) return 1;
}
}
else if(f[i].c=='B'){//象
int x=f[i].x,y=f[i].y;
for(int k=1;x-k>=1&&y-k>=1;k++){//左上方
if(x-k==sx&&y-k==sy) return 1;
if(ma.count({x-k,y-k})&&!t.flag[ma[{x-k,y-k}]]) break;
}
for(int k=1;x+k<=n&&y-k>=1;k++){//左下方
if(x+k==sx&&y-k==sy) return 1;
if(ma.count({x+k,y-k})&&!t.flag[ma[{x+k,y-k}]]) break;
}
for(int k=1;x-k>=1&&y+k<=n;k++){//右上方
if(x-k==sx&&y+k==sy) return 1;
if(ma.count({x-k,y+k})&&!t.flag[ma[{x-k,y+k}]]) break;
}
for(int k=1;x+k<=n&&y+k<=n;k++){//右下方
if(x+k==sx&&y+k==sy) return 1;
if(ma.count({x+k,y+k})&&!t.flag[ma[{x+k,y+k}]]) break;
}
}
else if(f[i].c=='Q'){//后
int x=f[i].x,y=f[i].y;
//车的部分
if(x==sx){
for(int j=y-1;j>=1;j--){//在左边
if(j==sy) return 1;
if(ma.count({x,j})&&!t.flag[ma[{x,j}]]) break;//遇到别的棋子就打断攻击范围
}
for(int j=y+1;j<=n;j++){//在右边
if(j==sy) return 1;
if(ma.count({x,j})&&!t.flag[ma[{x,j}]]) break;
}
}
if(y==sy){
for(int j=x-1;j>=1;j--){//在上边
if(j==sx) return 1;
if(ma.count({j,y})&&!t.flag[ma[{j,y}]]) break;
}
for(int j=x+1;j<=n;j++){//在下边
if(j==sx) return 1;
if(ma.count({x,j})&&!t.flag[ma[{j,y}]]) break;
}
}
//象的部分
for(int k=1;x-k>=1&&y-k>=1;k++){//左上方
if(x-k==sx&&y-k==sy) return 1;
if(ma.count({x-k,y-k})&&!t.flag[ma[{x-k,y-k}]]) break;
}
for(int k=1;x+k<=n&&y-k>=1;k++){//左下方
if(x+k==sx&&y-k==sy) return 1;
if(ma.count({x+k,y-k})&&!t.flag[ma[{x+k,y-k}]]) break;
}
for(int k=1;x-k>=1&&y+k<=n;k++){//右上方
if(x-k==sx&&y+k==sy) return 1;
if(ma.count({x-k,y+k})&&!t.flag[ma[{x-k,y+k}]]) break;
}
for(int k=1;x+k<=n&&y+k<=n;k++){//右下方
if(x+k==sx&&y+k==sy) return 1;
if(ma.count({x+k,y+k})&&!t.flag[ma[{x+k,y+k}]]) break;
}
}
else if(f[i].c=='X'){//王
int x=f[i].x,y=f[i].y;
int ddx[8]={-1,-1,-1,0,1,1,1,0},ddy[8]={-1,0,1,1,1,0,-1,-1};
for(int j=0;j<8;j++){//身边八个格子，找到了就能杀
if(in(x+ddx[j],y+ddy[j])&&x+ddx[j]==sx&&y+ddy[j]==sy) return 1;
}
}
else if(f[i].c=='P'){//兵
int x=f[i].x,y=f[i].y;
if(in(x+1,y-1)&&x+1==sx&&y-1==sy) return 1;
if(in(x+1,y+1)&&x+1==sx&&y+1==sy) return 1;//左右下方两个格子
}
}
return 0;
}
int main(){
while(cin>>n){
while(!q.empty()) q.pop();
ma.clear(),top=0;//初始化
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
cin>>c[i][j];
if(c[i][j]=='X') ex=i,ey=j;//存终点
if(c[i][j]=='O') a.x=i,a.y=j;//存起点
else if(c[i][j]!='.') f[++top]={c[i][j],i,j},ma[{i,j}]=top;//存入敌方棋子
fl[i][j]=0;//初始化
}
a.k=0;
for(int i=1;i<=55;i++) a.flag[i]=0;//初始化
q.push(a);//起点带着它的一大坨信息入队
bool flag=0;
while(!q.empty()){
node t=q.top();q.pop();
if(t.x==ex&&t.y==ey){//到终点了
cout<<t.k<<"\n";
flag=1;
break;
}
if(check(t)) continue;//被棋子吃掉
t.k++;
if(ma.count({t.x,t.y})) t.flag[ma[{t.x,t.y}]]=1;//吃掉棋子
for(int i=0;i<8;i++){//下一步走法
t.x+=dx[i],t.y+=dy[i];
if(in(t.x,t.y)&&!fl[t.x][t.y]){//能走且没走过
fl[t.x][t.y]=1,q.push(t);
}
t.x-=dx[i],t.y-=dy[i];
}
}
if(!flag) cout<<-1<<"\n";//不可能
}
return 0;
}