SP32088 CSTATE1 - Chessboard State 1 题解

FFTotoro · 2023-12-22 16:40:50 · 题解

放假了开始写大模拟。

本题就是判断某一方的王是否被将军 / 将死。

对于每种棋子写一个函数，输入一个坐标 (x,y)，返回一个存储 std::pair<int,int> 的 std::vector，表示该棋子一开始在 (x,y) 能走到哪些位置。

这样只要判断是不是有一方的某个棋子可以走到另一方的王的位置就可以判断将军。

至于将死，枚举应将方下一步的所有可能举动，每一种情况下判断王是否被将军即可。

有一个注意点，题面中提到了不需要也不应该考虑兵开始时走两格的情况，然而另一篇题解考虑了该情况，对读者产生了误导。Upd：现在改了。

放代码（代码较长，细节很多）：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> K(vector<string> &a,bool b,int x,int y){
  vector<pii> v;
  for(int dx:{-1,0,1})
    for(int dy:{-1,0,1})
      if(dx||dy){
        int xx=x+dx,yy=y+dy;
        if(~min(xx,yy)&&max(xx,yy)<8){
          if(a[xx][yy]=='.')v.emplace_back(xx,yy); // 空格
          else if(b?islower(a[xx][yy]):isupper(a[xx][yy])){
            v.emplace_back(xx,yy); break;
          } // 可以吃对方棋子，下同
        }
      }
  return v;
} // 王的走法
vector<pii> Q(vector<string> &a,bool b,int x,int y){
  vector<pii> v;
  for(int dx:{-1,0,1})
    for(int dy:{-1,0,1})
      if(dx||dy)
        for(int k=1;k<8;k++){
          int xx=x+dx*k,yy=y+dy*k;
          if(~min(xx,yy)&&max(xx,yy)<8){
            if(a[xx][yy]=='.')v.emplace_back(xx,yy);
            else if(b?islower(a[xx][yy]):isupper(a[xx][yy])){
              v.emplace_back(xx,yy); break;
            }
          }
          else break;
        }
  return v;
} // 后的走法
vector<pii> R(vector<string> &a,bool b,int x,int y){
  vector<pii> v;
  for(int dx:{-1,0,1})
    for(int dy:{-1,0,1})
      if(abs(dx)!=abs(dy))
        for(int k=1;k<8;k++){
          int xx=x+dx*k,yy=y+dy*k;
          if(~min(xx,yy)&&max(xx,yy)<8){
            if(a[xx][yy]=='.')v.emplace_back(xx,yy);
            else if(b?islower(a[xx][yy]):isupper(a[xx][yy])){
              v.emplace_back(xx,yy); break;
            }
          }
          else break;
        }
  return v;
} // 车的走法
vector<pii> N(vector<string> &a,bool b,int x,int y){
  vector<pii> v;
  for(int dx:{-2,-1,1,2})
    for(int dy:{-2,-1,1,2})
      if(abs(dx)!=abs(dy)){
        int xx=x+dx,yy=y+dy;
        if(min(xx,yy)>=0&&max(xx,yy)<8){
          if(a[xx][yy]=='.')v.emplace_back(xx,yy);
          else if(b?islower(a[xx][yy]):isupper(a[xx][yy])){
            v.emplace_back(xx,yy); break;
          }
        }
      }
  return v;
} // 马的走法
vector<pii> B(vector<string> &a,bool b,int x,int y){
  vector<pii> v;
  for(int dx:{-1,1})
    for(int dy:{-1,1})
      for(int k=1;k<8;k++){
        int xx=x+dx*k,yy=y+dy*k;
        if(~min(xx,yy)&&max(xx,yy)<8){
          if(a[xx][yy]=='.')v.emplace_back(xx,yy);
          else if(b?islower(a[xx][yy]):isupper(a[xx][yy])){
            v.emplace_back(xx,yy); break;
          }
        }
        else break;
      }
  return v;
} // 象的走法
vector<pii> P(vector<string> &a,bool b,int x,int y){
  vector<pii> v;
  if(b){
    if(x){
      if(a[--x][y]=='.'){
        v.emplace_back(x,y);
        if(x==5&&a[x-1][y]=='.')
          v.emplace_back(x-1,y);
      }
      for(int yy:{y-1,y+1})
        if(~yy&&yy<8&&islower(a[x][yy]))
          v.emplace_back(x,yy);
    }
  }
  else{
    if(x<7){
      if(a[++x][y]=='.'){
        v.emplace_back(x,y);
        if(x==2&&a[x+1][y]=='.')
          v.emplace_back(x+1,y);
      }
      for(int yy:{y-1,y+1})
        if(~yy&&yy<8&&isupper(a[x][yy]))
          v.emplace_back(x,yy);
    }
  }
  return v;
} // 兵的走法
bool check(bool b,vector<string> &a){
  vector<vector<bool> > t(8,vector<bool>(8)); pii kp;
  for(int i=0;i<8;i++)
    for(int j=0;j<8;j++)
      if(b?isupper(a[i][j]):islower(a[i][j])){
        vector<pii> v;
        switch(a[i][j]){
          case 'K':case 'k':v=K(a,b,i,j); break;
          case 'Q':case 'q':v=Q(a,b,i,j); break;
          case 'R':case 'r':v=R(a,b,i,j); break;
          case 'H':case 'h':v=N(a,b,i,j); break;
          case 'B':case 'b':v=B(a,b,i,j); break;
          case 'P':case 'p':v=P(a,b,i,j); break;
        }
        for(auto [x,y]:v)t[x][y]=true;
      } // 枚举每个棋子判断将军
      else if(a[i][j]=='K'||a[i][j]=='k')kp=make_pair(i,j);
  return t[kp.first][kp.second];
} // 判断将军
int pd(vector<string> &a){
  bool x=check(0,a),y=check(1,a);
  if(x&&y)return -1;
  if(!x&&!y)return 0;
  return x?1:2;
} // 判断局面
bool checkmate(bool b,vector<string> &a){
  for(int i=0;i<8;i++)
    for(int j=0;j<8;j++)
      if(b?islower(a[i][j]):isupper(a[i][j])){
        vector<pii> v;
        switch(a[i][j]){
          case 'K':case 'k':v=K(a,!b,i,j); break;
          case 'Q':case 'q':v=Q(a,!b,i,j); break;
          case 'R':case 'r':v=R(a,!b,i,j); break;
          case 'H':case 'h':v=N(a,!b,i,j); break;
          case 'B':case 'b':v=B(a,!b,i,j); break;
          case 'P':case 'p':v=P(a,!b,i,j); break;
        }
        for(auto [x,y]:v){
          auto c=a; c[i][j]='.',c[x][y]=a[i][j];
          if(!check(b,c))return false;
        }
      } // 枚举下一步所有可能局面
  return true;
} // 判断将死
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    vector<string> a(8);
    for(auto &i:a)cin>>i;
    switch(pd(a)){
      case -1:cout<<"Impossible\n"; break;
      case 0:cout<<"Safe\n"; break;
      case 1:cout<<"Black Check";
        if(checkmate(0,a))cout<<"mate";
        cout<<endl; break;
      case 2:cout<<"White Check";
        if(checkmate(1,a))cout<<"mate";
        cout<<endl; break;
    }
  }
  return 0;
}