炸飞机（plane）

题目描述

下载文件自己想办法测评

炸飞机是一款双人对战游戏。游戏双方初始各有一张 $12\times 12$ 的格子纸。格子左上角为格子 $(1,1)$，左下角为坐标 $(n,1)$，右上角为坐标 $(1,n)$。飞机是一个可旋转的形状固定的四连通连通块，其中有一个特殊的格子，称之为机头，其余格子称为机身。游戏开始前，会通过掷硬币的方式决定先后手。接着，每个玩家需要在自己的格子纸上不重叠地画 $3$ 架飞机。飞机有多种型号，各型号飞机的形状见文末提示处。之后，两名选手将轮流进行以下操作：

选择以下两个操作之一进行：

1. 打击操作：询问对方的格子纸中的方格 $(i,j)$ 上是机头，还是机身，还是都不是。如果是机头，将击毁该机头所在的飞机。之后，对方会得知你所询问的 $i,j$。

2. 移动操作：将自己的第 $i$ 架飞机向某个方向平移一格。你需要保证此时你的这架飞机未被击毁，且移动过后仍与其他飞机并不重叠（包括已经被击毁的飞机）。之后，对手将检测到气流流动的改变，得知你移动的方向，但是不知道你移动的是哪一架飞机。

最先击毁对方三架飞机的玩家为胜者。每名玩家最多各自进行 $500$ 次操作。如果 $500$ 次操作后仍未分出胜负，则后手获得胜利。

你需要设计一个程序，来使自己尽可能地成为游戏的胜者。

实现方式

在一次程序运行的过程中，总共会进行 $T$ 次游戏。

本题采用函数交互的形式。

下文给出 C++ 的实现方法。其他语言的实现方法与 C++ 类似，详情参考下发文件中的示例文件与示例代码。

下文中认为飞机标号和型号均从 $0$ 开始标号。

你不需要，也不应该实现主函数。

你应确保提交的程序包含头文件 game.h，可在程序开头加入以下代码实现：

#include "game.h"

选手可以调用以下三个函数：

void Draw(int kind,int direction,int x,int y)

你只能在 Init 函数中调用这个函数。你可以通过调用这个函数来放置一架飞机。$kind$ 为飞机的型号，$direction$ 只能是 $0,1,2,3$ 的一个，分别表示飞机不进行旋转，顺时针旋转 $90$ 度，顺时针旋转 $180$ 度，顺时针旋转 $270$ 度。$x,y$ 分别表示飞机的第一维坐标和第二维坐标。你需要保证飞机之间不会产生重叠，且飞机没有出界。

int Hit(int x,int y)

你只能在 Operate_self 函数中调用这个函数。你可以通过调用这个函数来进行一次打击操作。$x,y$ 分别表示选手希望询问的第一维坐标与第二维坐标。该函数会返回 $0,1,2$ 中的一个。如果返回 $0$，则对手的方格 $(x,y)$ 上为空白；如果返回 $1$，则对手的方格 $(x,y)$ 上为机身。如果返回 $2$，则对手的方格 $(x,y)$ 上为机头。

void Move(int id,int direction)

你只能在 Operate_self 函数中调用这个函数。你可以通过调用这个函数来进行一次移动操作。$id$ 表示移动的飞机的编号。$direction$ 应为 $0,1,2,3$ 中的一个，分别表示你将飞机向上、右、下、左移动一格。对于机头原本在 $(x,y)$ 的飞机，向上、右、下、左移动后机头的位置分别为：$(x-1,y),(x,y+1),(x+1,y),(x,y-1)$。你需要保证你移动的飞机未被击中机头，且移动后飞机不会产生重叠与出界。

选手需要实现以下三个函数：

void Init(int last,int id,vector<int> type,bool b);

• $last$ 表示上一把游戏的胜负情况。如果上一把获胜，$last=1$。如果上一把失败，$last=0$。如果这是第一把游戏，$last=2$。

• $id$ 表示子任务的编号

• $type$ 中一共有三个元素。$type_i$ 在二进制下的从低到高第 $j$ 位（从 $0$ 开始标号）如果为 $1$，则第 $i$ 架飞机可选用型号 $j$，否则第 $i$ 架飞机不能选用型号 $j$。

• $b$ 为 $1$ 表示你是先手，否则你是后手。

该函数会在每场游戏开始前被调用一次。你必须在 Init 中调用恰好三次 Draw 函数，第 $i$ 次调用表示放置编号为 $i-1$ 的飞机。

void Operate_self();

该函数会在轮到你操作时被调用一次。你必须在 Operate_self 中调用一次 Hit 或 Move 函数。你不能在一次 Operate_self 的运行过程中同时调用 Hit 和 Move。在一次 Operate_self 的运行过程中，Hit和 Move 都至多只能调用一次。

void Operate_opponent(bool kind,int x,int y);

该函数会在对手操作后被调用一次。如果 $kind$ 为 $0$，则对手刚刚进行了一次打击操作，且询问了位置 $(x,y)$。否则对手刚刚进行了一次移动操作，当 $x=0,1,2,3$ 时分别意味着对手将某架飞机向上移动一格，向右移动一格，向下移动一格，向左移动一格。对于机头原本在 $(x,y)$ 的飞机，向上、右、下、左移动后机头的位置分别为：$(x-1,y),(x,y+1),(x+1,y),(x,y-1)$。

如果某人在某个测试点运行过程中出现了 re,tle,mle 或非法的函数调用，则该测试点所有数据均判定为对手胜利。如果两人在某个测试点运行过程中均出现 re,tle,mle 或非法的函数调用，则无法保证该测试点最终结果。

测试点

下文中 $type_0,type_1,type_2$ 均以二进制形式给出。

测试点编号	$id=$	$T=$	$type_0=$	$type_1=$	$type_2=$	分值
$1$		$20$	$000001$			$10$
$2$			$000010$		$000010$	$30$
$3$					$001100$	$35$
$4$			$100011$		$011100$	$20$
$5$			$100000$			$5$

为降低一部分运气对结果的影响，保证在每个测试点的 $20$ 组数据中对于每位玩家均有 $10$ 次先手，$10$ 次后手。

保证交互库的运行时间不会超过 1s。

测试方式

下文给出 C++ 的实现方法。其他语言的实现方法与 C++ 类似，详情参考下发文件中的示例文件与示例代码。

你需要打开 grader.cpp 的源代码。用你的代码替换 namespace player 中的注释部分，并用对手的代码替换 namespace opponent 中的注释部分。将 grader.cpp 编译得到可执行文件。

在可执行文件中，你需要输入一行四个整数 $id,type_0,type_1,type_2$。之后，将会进行 $1$ 局游戏。之后，将根据双方程序运行结果，给出对应的反馈。特别的，反馈中的 player0 指代你的代码，player1 指代对手的代码。

下发文件中的 sample.cpp 给出了一种满足子任务 $5$ 要求的实现方式。如果你希望你的代码和对手的代码均为 sample.cpp，则你按上述方法修改 grader.cpp 得到的新程序应类似于 grader_sample.cpp。你可以直接编译运行 grader_sample.cpp，按上述格式输入得到两个 sample.cpp 的对战反馈。

评分方式

对于接下来的内容，选手不必了解所有细节，建议只阅读加粗的部分，但如果有兴趣还是可以详细了解。

本题不采取即时反馈赛制。 在比赛正式开始后，每经过 $30$ 分钟，评测机将执行一次批量评测。具体而言，对于每位选手，评测机将会取其最后一次提交且编译成功的代码作为有效提交。在每次批量评测前 5 分钟，将会有通知提醒选手及时提交参与本次批量评测的代码，请选手务必注意提交的时机。

本题采用 Elo rating 对选手程序进行排名与计算分数。每个测试点都有独立的 rating 和排名，选手可以针对某几个测试点特别优化自己的程序以获得较高的分数。

在一次批量评测中，对于每个测试点，每份代码的 初始 rating 为 $1500$，然后评测机会组织若干轮匹配赛（$30$ 轮左右），每轮匹配赛中将采取如下方式确定每位选手的对手：

1. 所有选手的顺序将被完全打乱。
2. 依次遍历每位尚未匹配的选手，尝试采用如下机制寻找对手：
   1. 初始匹配窗口为 $100$。
   2. 每次查询尚未匹配的选手中，rating 与当前选手差距不大于匹配窗口的选手。如果有多个选手，随机抽取一个作为当前选手的对手，当前选手匹配完毕。
   3. 如果不存在这样的选手，将匹配窗口扩大 $50$ 并转至步骤 ii，直至匹配窗口到达上限 $600$。
   4. 如果最终匹配失败，当前选手记为轮空，不参与本轮匹配赛。

在一次对战中，设两名选手分别为 $A$ 和 $B$，设 $A,B$ 当前的 rating 分别为 $R_A$ 与 $R_B$。定义 $E_A = \frac{1}{1 + 10^{(R_B - R_A)/400}},E_B=\frac{1}{1 + 10^{(R_A - R_B)/400}}$。令 $S_A$ 和 $S_B$ 分别为 $A$ 与 $B$ 在此次对战中该测试点的胜率。对战后，双方在该测试点 rating 将被更新为 $R_A',R_B'$，计算方式如下：

$$R_A' = R_A + K (S_A - E_A) \\ R_B' = R_B + K (S_B - E_B) $$

其中 $K=40 \times 4^{-i/t}$，$i$ 为当前是第几轮匹配赛，$t$ 为匹配赛的总轮数。

所有匹配赛轮次结束后，选手在每个测试点的 rating 也即确定。接下来进入分数统计环节。我们采用赋分制将选手的 rating 转化为分数，其机制如下：

对于每个测试点，我们会先按 rating 从高到低对选手排序，将选手分为 A,B,C,D,E 五档。

等级	排名范围	分数比例范围
A	$0\% \sim 10\%$	$0.85 \sim 1$
B	$10\% \sim 40\%$	$0.6 \sim 0.85$
C	$40\% \sim 70\%$	$0.35 \sim 0.6$
D	$70\% \sim 90\%$	$0.2 \sim 0.35$
E	$90\% \sim 100\%$	$0.05 \sim 0.2$

每位选手在该测试点的分数计算公式为：

$$\text{score}=\mathrm{fullScore} \times (\mathrm{minRatio} + (\mathrm{maxRatio}-\mathrm{minRatio}) \times \frac{\mathrm{rating}-\mathrm{minRating}}{\mathrm{maxRating}-\mathrm{minRating}}) $$

其中，$\mathrm{fullScore}$ 为该测试点的分值，$\mathrm{rating}$ 为当前选手在本测试点的 rating，$\mathrm{minRatio},\mathrm{maxRatio}$ 为选手所处档次的分数比例的下限与上限，$\mathrm{minRating},\mathrm{maxRating}$ 为选手所处档次的所有选手中 rating 的最小值与最大值。

例：某位选手在测试点 1（满分 $20$ 分）的 rating 为 $1530$，处于 C 档，该档次的选手中 rating 最高 $1540$，最低 $1440$，根据上述公式计算出该选手在测试点 1 的得分为 $20 \times (0.35+0.25 \times 0.9)=11.5$ 分。

在本次批量评测中，选手的最终得分为各测试点得分之和。选手可以通过分数的详情页面了解各测试点的得分、rating 及排名。

比赛结束后，为了更准确地确定选手的表现与排名，我们可能会进行额外的若干轮匹配赛。

在一次批量评测开始时，评测机会自动将上一次的提交复制一份，用于下一次批量评测。此次批量评测结束后，选手可以在原来的提交中看到此次批量评测的得分。

选手在该题的最终得分为最后一次批量评测后的选手得分（而非历史最高分）。新的提交会覆盖旧的提交，建议选手提交代码前确定新代码相对于旧代码的优劣，如采用自我对打等方式。

提示

飞机的各种机型在不进行旋转的模样如下：

机型 $0$：

机型 $1$：

机型 $2$：

机型 $3$：

机型 $4$：

机型 $5$：