自动搬运

查看原文

来自洛谷，原作者为

	CashCollectFactory 这个家伙不懒，但什么都留下了

搬运于2025-08-24 22:19:02，当前版本为作者最后更新于2023-11-20 22:10:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

有一种叫 Checkers 的棋类游戏，有一系列棋谱，要通过棋谱还原出原来的可能的局面。 规则如下：

1. 棋子分为两种，小兵和大王，兵只能往前斜走，王能往回走，隔着对方的子跳过去能吃棋。
2. 兵到了对面底线能晋升王。
3. 如果当前局面能吃子，必须先吃子。

（原本题目翻译里面什么白人男子、黑人国王的机翻实在让人迷茫）

火力全开的大模拟解法

题目算法不难，难处在于实现上有特别多细节需要注意。

首先我们需要正序遍历一遍棋谱，把棋谱上移动了的棋子但棋盘上没有的摆上去。摆的时候，优先摆小兵（因为移动方向只有2个，后面检查 jump 优先的时候更方便），不符合规则才换成国王，并且把 jump 中被吃掉的子也补上，同时也要处理吃子和晋升的情况。

接下来是检查局面是否符合 jump 优先的规则，再次正序跑一遍棋谱，如果有不符合的情况，需要用一些从头到尾未被移动过的棋子去挡住这个可能 jump 的路线。由于不确定这个位置是放黑棋还是白棋，所以两种情况都要递归地试一下。 由于棋盘只有 $32$ 个位置，问题规模较小，所以实际上对时间复杂度的影响不大。

还有一些具体的实现方法，就都放在代码中啦。

代码时间（码丑勿喷）

代码中没有用什么特别的卡常手段，但目前已经是全谷最优解啦，卡常大师可以试试再优化一手哦~

#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 ”这个新东西~