火力全开大模拟怒拔最优解！
CashCollectFactory · · 题解
题目大意
有一种叫 Checkers 的棋类游戏，有一系列棋谱，要通过棋谱还原出原来的可能的局面。 规则如下：
- 棋子分为两种，小兵和大王，兵只能往前斜走，王能往回走，隔着对方的子跳过去能吃棋。
- 兵到了对面底线能晋升王。
- 如果当前局面能吃子，必须先吃子。
（原本题目翻译里面什么白人男子、黑人国王的机翻实在让人迷茫）
火力全开的大模拟解法
题目算法不难，难处在于实现上有特别多细节需要注意。
首先我们需要正序遍历一遍棋谱，把棋谱上移动了的棋子但棋盘上没有的摆上去。摆的时候，优先摆小兵（因为移动方向只有2个，后面检查 jump 优先的时候更方便），不符合规则才换成国王，并且把 jump 中被吃掉的子也补上，同时也要处理吃子和晋升的情况。
接下来是检查局面是否符合 jump 优先的规则，再次正序跑一遍棋谱，如果有不符合的情况，需要用一些从头到尾未被移动过的棋子去挡住这个可能 jump 的路线。由于不确定这个位置是放黑棋还是白棋，所以两种情况都要递归地试一下。 由于棋盘只有
还有一些具体的实现方法，就都放在代码中啦。
代码时间（码丑勿喷）
代码中没有用什么特别的卡常手段，但目前已经是全谷最优解啦，卡常大师可以试试再优化一手哦~
#include <bits/stdc++.h>
using namespace std;
char startPlayer;
vector<char> moveType;
vector<vector<int>> moves;
inline char opp(char player) { return player == 'W' ? 'B' : 'W'; }
inline int sqX(int sq) { return (sq-1)%4*2 + 1-((sq-1)/4)%2; }
inline int sqY(int sq) { return (sq-1)/4; }
pair<vector<string>, vector<string>> doit(vector<string> start) {
vector<string> board = start;
char player = startPlayer;
for (int i = 0; i < moves.size(); i++, player = opp(player))
for (int j = 0; j+1 < moves[i].size(); j++) {
int sx = sqX(moves[i][j ]), sy = sqY(moves[i][j]);
int ex = sqX(moves[i][j+1]), ey = sqY(moves[i][j+1]);
bool promoted = ((player == 'W' && ey == 0) || (player == 'B' && ey == 7)) && islower(board[sy][sx]);
if (moveType[i] == '-') {
for (int y = 0; y < 8; y++)
for (int x = 0; x < 8; x++) if (toupper(board[y][x]) == player)
for (int dx = -1; dx <= 1; dx += 2)
for (int dy = -1; dy <= 1; dy += 2) {
if (board[y][x] == 'w' && dy == 1) continue;
if (board[y][x] == 'b' && dy == -1) continue;
int x2 = x+dx+dx, y2 = y+dy+dy;
if (x2 < 0 || x2 >= 8 || y2 < 0 || y2 >= 8) continue;
if (toupper(board[y+dy][x+dx]) != opp(player)) continue;
if (board[y2][x2] == '.')
return {{}, {}};
if (board[y2][x2] == '?') {
start[y2][x2] = (y2 == 0) ? 'W' : 'w';
auto ret = doit(start);
if (ret.first.size())
return ret;
start[y2][x2] = (y2 == 7) ? 'B' : 'b';
return doit(start);
}
}
}
board[ey][ex] = board[sy][sx];
if (promoted) board[ey][ex] = toupper(board[ey][ex]);
board[sy][sx] = '.';
if (moveType[i] == 'x') {
int mx = (sx+ex)/2, my = (sy+ey)/2;
board[my][mx] = '.';
if (j+2 == moves[i].size() && !promoted) {
int x = ex, y = ey;
for (int dx = -1; dx <= 1; dx += 2)
for (int dy = -1; dy <= 1; dy += 2) {
if (board[y][x] == 'w' && dy == 1) continue;
if (board[y][x] == 'b' && dy == -1) continue;
int x2 = x+dx+dx, y2 = y+dy+dy;
if (x2 < 0 || x2 >= 8 || y2 < 0 || y2 >= 8) continue;
if (toupper(board[y+dy][x+dx]) != opp(player)) continue;
if (board[y2][x2] == '.')
return {{}, {}};
if (board[y2][x2] == '?') {
start[y2][x2] = (y2 == 0) ? 'W' : 'w';
auto ret = doit(start);
if (ret.first.size())
return ret;
start[y2][x2] = (y2 == 7) ? 'B' : 'b';
return doit(start);
}
}
}
}
}
return {start, board};
}
int main() {
int N, first = 1;
while (cin >> startPlayer >> N) {
moveType = vector<char>(N);
moves = vector<vector<int>>(N);
for (int i = 0; i < N; i++) {
string s;
cin >> s;
int j = 0;
for (;;) {
int sq = s[j]-'0';
if (j+1 < s.size() && isdigit(s[j+1])) sq = 10*sq + s[++j]-'0';
moves[i].push_back(sq);
if (++j == s.size()) break;
moveType[i] = s[j++];
}
}
vector<string> start(8, "????????"), board = start;
char player = startPlayer;
vector<vector<int>> startX(8), startY(8);
for (int y = 0; y < 8; y++)
for (int x = 0; x < 8; x++) {
startX[y].push_back(x);
startY[y].push_back(y);
}
for (int i = 0; i < moves.size(); i++, player = opp(player))
for (int j = 0; j+1 < moves[i].size(); j++) {
int sx = sqX(moves[i][j ]), sy = sqY(moves[i][j ]);
int ex = sqX(moves[i][j+1]), ey = sqY(moves[i][j+1]);
bool promoted = ((player == 'W' && ey == 0) || (player == 'B' && ey == 7));
if (board[sy][sx] == '?') {
board[sy][sx] = start[sy][sx] = tolower(player);
}
if (board[ey][ex] == '?') {
board[ey][ex] = start[ey][ex] = '.';
}
assert(toupper(board[sy][sx]) == player);
assert(board[ey][ex] == '.');
if (((player == 'W') ^ (ey < sy)) && islower(board[sy][sx])) {
board[sy][sx] = start[startY[sy][sx]][startX[sy][sx]] = toupper(board[sy][sx]);
}
board[ey][ex] = board[sy][sx];
if (promoted && j+2 == moves[i].size()) board[ey][ex] = toupper(board[ey][ex]);
board[sy][sx] = '.';
startX[ey][ex] = startX[sy][sx];
startY[ey][ex] = startY[sy][sx];
if (moveType[i] == 'x') {
int mx = (sx+ex)/2, my = (sy+ey)/2;
if (board[my][mx] == '?') {
board[my][mx] = start[my][mx] = tolower(opp(player));
}
assert(toupper(board[my][mx]) == opp(player));
board[my][mx] = '.';
}
}
auto ret = doit(start);
assert(ret.first.size());
if (!first) cout << endl;
first = false;
for (int y = 0; y < 8; y++)
for (int x = y%2; x < 8; x += 2) {
ret.first[y][x] = ret.second[y][x] = '-';
}
for (int y = 0; y < 8; y++)
for (int x = 1-y%2; x < 8; x += 2) {
if (ret.first[y][x] == '?') ret.first[y][x] = '.';
if (ret.second[y][x] == '?') ret.second[y][x] = '.';
}
for (int y = 0; y < 8; y++) cout << ret.first[y] << ' ' << ret.second[y] << endl;
}
return 0;
}补充一句，本代码需要使用 C++11 以上版本才可以正常编译，只因里面用了“ auto ”这个新东西~