[EC Final 2022] Chinese Checker 题解

· · 题解

前言

暑假集训的时候 @RSY 搞的神题，当时读错题目 100\rightarrow 20，前两周补完了题，来补个题解。

大部分人这题的代码都写得很抽象，毕竟是阴间模拟题。个人觉得自己的思路和写的代码都相对较为简洁。

解法

尝试对于中国跳棋棋盘建立坐标系，本人的方法为将行数作为坐标的第一关键字，所有与蓝色的左上角与最下方那个红色的点的连线平行的线上的点的第二关键字相等，一列一列从左到右第二关键字依次加一（建系方法很多，可以自行画图理解一下），并且令左下角那个粉红色的点的坐标第二关键字为 1。

将输入的坐标 (x,y) 转化为这个坐标系下的坐标也是容易的：第一关键字 x 不变，令它所在的那一行的第二关键字最小的为 l_x，最大的为 r_x，那么 y\leftarrow y+l_x-1。后面判断一个点是否在棋盘内也可以使用上面的 l 和 r：先判断 x 坐标在不在范围内，如果在再判断 y 是否满足 l_x\le y\le r_x。

于是可以走的 6 个方向就可以确定，它们的 (\Delta x,\Delta y) 分别为 (-1,0),(1,0),(0,-1),(0,1),(-1,1),(1,-1)。

假设给定了要跳的棋子，考虑怎么处理跳的过程：枚举 6 个方向，再枚举到“跳台”（就是中间那个棋子）的步数，如果该点在棋盘上、正好有一个棋子可以作为“跳台”且中间无阻挡，就再判断目标点的条件（可以类比自行理解）。

到了这一步就不难了，枚举要跳的那个棋子然后爆搜。记得在搜索过程中打标记（不要跳回去）。

可以用 std::set 存储棋子位置。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int l[18]={0,13,12,11,10,5,5,5,5,5,4,3,2,1,5,5,5,5}, // 左边界
  r[18]={0,13,13,13,13,17,16,15,14,13,13,13,13,13,8,7,6,5}, // 右边界 
  dx[6]={-1,1,0,0,-1,1},dy[6]={0,0,-1,1,1,-1}; // 方向数组
set<pii> m,s;
pair<pii,int> jump(pii a,int d,int s,int c=0){
  while(s--){
    a.first+=dx[d],a.second+=dy[d];
    if(m.find(a)!=m.end())c++; // 数经过的棋子数（判断中间有没有其他棋子）
  }
  return make_pair(a,c);
} // 模拟跳的过程
bool check(pii a){
  auto [x,y]=a;
  return x>0&&x<=17&&y>=l[x]&&y<=r[x];
} // 判断是否在棋盘内
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,c=0; cin>>n;
    vector<pii> a(n);
    for(auto &[x,y]:a)cin>>x>>y,y+=l[x]-1;
    m.clear(); for(pii i:a)m.emplace(i);
    function<void(int)> dfs=[&](int i){
      s.emplace(a[i]); // 打标记
      for(int j=0;j<6;j++)
        for(int k=1;k<=6;k++)
          if(auto [p,c1]=jump(a[i],j,k);c1==1&&check(p)&&m.find(p)!=m.end())
          // 跳台的条件
            if(auto [e,c2]=jump(p,j,k);!c2&&check(e)&&m.find(e)==m.end()){ 
            // 目标点的条件
              pii t=a[i];
              m.erase(a[i]),m.emplace(a[i]=e);
              if(s.find(a[i])==s.end())dfs(i); 
              // 满足条件继续搜
              m.erase(e),m.emplace(a[i]=t);
            }
    };
    for(int i=0;i<n;i++,s.clear())
      dfs(i),c+=s.size()-1; // 枚举每一个点，统计答案
    cout<<c<<endl;
  }
  return 0;
}