CF1658E Gojou and Matrix Game

Marin 在经历了一整天的 Cosplay 后感到非常疲惫，于是 Gojou 邀请她玩一个游戏！ Marin 和 Gojou 轮流在一个 $n \times n$ 的棋盘上放置自己的棋子，Marin 先手。棋子的放置有如下限制和规定： - 除了第一步之外，每位玩家放置的棋子必须与上一步放置的棋子在曼哈顿距离上大于 $k$。也就是说，如果某位玩家将棋子放在 $(x_1, y_1)$，那么下一步对方只能将棋子放在满足 $|x_2 - x_1| + |y_2 - y_1| > k$ 的格子 $(x_2, y_2)$ 上。 - 除了上述限制外，棋子可以放在棋盘上的任意位置，包括之前任何玩家已经放置过棋子的格子。 每当某位玩家在 $(x, y)$ 处放置棋子时，该玩家获得 $v_{x, y}$ 分数。棋盘上所有 $v$ 的值都互不相同。即使某个格子已经被放置过棋子，再次放置仍然可以获得分数。游戏在每位玩家都进行了 $10^{100}$ 步后结束。 Marin 和 Gojou 将进行 $n^2$ 局游戏。对于棋盘上的每一个格子，都会有一局游戏以 Marin 在该格子作为第一步开始。请你回答，对于每一局游戏，如果 Marin 和 Gojou 在之后都采取最优策略，最终谁的得分更高？或者游戏是否平局（两人得分相同）？

第一行包含两个整数 $n$、$k$（$3 \le n \le 2000$，$1 \leq k \leq n - 2$）。保证在这些限制下总是可以进行下一步操作。 接下来 $n$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 个整数为 $v_{i,j}$（$1 \le v_{i,j} \le n^2$）。所有 $v$ 的值互不相同。

你需要输出 $n$ 行。第 $i$ 行输出 $n$ 个字符，第 $j$ 个字符表示以 $(i, j)$ 作为 Marin 首步的那一局的结果。若 Marin 获胜输出 'M'，若 Gojou 获胜输出 'G'，若平局输出 'D'。每行字符之间不添加空格。

由 ChatGPT 4.1 翻译