CF1557E Assiut Chess
前言
这篇题解可能会和普通题解不太一样，会很“生动”，希望大家喜欢~
解题思路
我们的主角是国王（K）和王后（Q），那就把舞台交给他们吧！
旁白：这一天王后发现国王藏私房钱，于是决定抓住他（什么辣鸡剧情啊喂！）。国王和王后移动方式见题目，国王率先进入棋盘，选择了一个位置，现在王后进场了……
Q：哼，反正我的攻击距离远，让让他。我就在 \((1,1)\) 好啦。反正不管哪个位置开始，我都能抓住他。
K：别说大话！
Q：等着瞧！我现在不知道你在哪里，但我只要保证你一直在我下方就可以了！我该什么时候下移呢？如果我在 \(i\) 行，这个糟老头子在 \(i+1\) 行，那么我往下，他可以往上，所以，我一定要确保我和他的距离在 \(2\) 行以上才能向下一行。怎么做到这一点呢？真实伤脑筋。
K：嘿嘿！你抓不到我的！你就慢慢想吧！我先走一步喽！
Q：啊！我知道了，只要我从这一行 \((i,1)\) 位置出发，每次把这一行巡逻一遍，由于国王没法移动两格，一定一直在我的右边，为了不被我抓住，一定会向下逃走的！一旦他向下，我就向下，你跑不了！
旁白：A few moments later.
K：坏了，再这样下去，我一定会输的，她最多只需要 \(8*8=64\) 步就够了。我不能一直往下，我可以先跑到离她相对较远的地方，然后往上到 \(i+1\) 行！这样她就乱了阵脚了哈哈哈。只要我往上，她就没办法。
Q：糟了，这该怎么办？我不知道他现在是否在 \(i+1\)? 行，只能再巡逻一次了，但是他一直这样往怎么办，我的步数就要变成了 \((8+x)*8\)? 次了（\(x\)? 表示 K 往上的次数）。不对，\(x\) ?好像是有范围的，他最多只能往上 \(7\) 次，那么我的巡逻次数最多是 \(120\) 次。老娘完全不虚你~
旁白：最后王后抓住了国王，拿回了他的钱。The End！！！
不知道这样的形式怎么样，我也不知道怎么心血来潮就写成这样了。。。。
反正核心思想就是关注国王的竖向移动，一旦往下，我们就往下，一旦往上，我们就重新巡逻这一行，由于国王最多往上 \(7\) 次，我们一定抓得住他。至于为什么是 \(7\) 次，读者自证不难
代码
//Don‘t act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you‘ll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<‘0‘||ch>‘9‘) {
if(ch==‘-‘)
f=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘) {
x=x*10+ch-‘0‘;
ch=getchar();
}
return f*x;
}
const int MAXN=131;
int n,pos;
string PLA(int x,int y) {
if(x==0||y==0) {
puts("???");
}
//please let me know the answer (((
printf("%d %d\n",x,y);
pos=y;
//fflush(stdout);
string s;
cin>>s;
return s;
}
bool patrol(int x) {
for(int i=(pos==1? 2:1);i<=8;i++) {
string s=PLA(x,i);
if(s=="Done") {
return 1;
}
if(s[0]==‘D‘) {
return 0;
}
if(s[0]==‘U‘) {
return patrol(x);
}
}
return 0;
}
void work() {
pos=1;
for(int i=1;i<=8;i++) {
if(PLA(i,pos)=="Done") {
return ;
}
if(patrol(i)) {
return ;
}
}
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int t=read();
while(t--) {
work();
}
//fclose(stdin);
//fclose(stdout);
return 0;
}