Gojou and Matrix Game

题意翻译

现在有一个大小为 $n\times n$ 的棋盘，其中不重不漏地填有 $1$ 至 $n^2$ 的所有整数。M 和 G 会玩以下游戏：M 先将一枚棋子放在某个初始格子中，随后从 G 开始双方会轮流移动棋子，每次将棋子移动到与当前格子曼哈顿距离大于 $k$ 的格子中并获得该格子中数字的分数（一个格子可以被访问多次）。经过 $10^{100}$ 轮后分数较多者获胜。对于每种 M 放初始格子的方案，求谁会获胜。$n\le 2\times 10^3,1\le k\le n-2$。

题目描述

Marin feels exhausted after a long day of cosplay, so Gojou invites her to play a game! Marin and Gojou take turns to place one of their tokens on an $ n \times n $ grid with Marin starting first. There are some restrictions and allowances on where to place tokens: - Apart from the first move, the token placed by a player must be more than Manhattan distance $ k $ away from the previous token placed on the matrix. In other words, if a player places a token at $ (x_1, y_1) $ , then the token placed by the other player in the next move must be in a cell $ (x_2, y_2) $ satisfying $ |x_2 - x_1| + |y_2 - y_1| > k $ . - Apart from the previous restriction, a token can be placed anywhere on the matrix, including cells where tokens were previously placed by any player. Whenever a player places a token on cell $ (x, y) $ , that player gets $ v_{x,\ y} $ points. All values of $ v $ on the grid are distinct. You still get points from a cell even if tokens were already placed onto the cell. The game finishes when each player makes $ 10^{100} $ moves. Marin and Gojou will play $ n^2 $ games. For each cell of the grid, there will be exactly one game where Marin places a token on that cell on her first move. Please answer for each game, if Marin and Gojou play optimally (after Marin's first move), who will have more points at the end? Or will the game end in a draw (both players have the same points at the end)?

输入输出格式

输入格式

The first line contains two integers $ n $ , $ k $ ( $ 3 \le n \le 2000 $ , $ 1 \leq k \leq n - 2 $ ). Note that under these constraints it is always possible to make a move. The following $ n $ lines contains $ n $ integers each. The $ j $ -th integer in the $ i $ -th line is $ v_{i,j} $ ( $ 1 \le v_{i,j} \le n^2 $ ). All elements in $ v $ are distinct.

输出格式

You should print $ n $ lines. In the $ i $ -th line, print $ n $ characters, where the $ j $ -th character is the result of the game in which Marin places her first token in the cell $ (i, j) $ . Print 'M' if Marin wins, 'G' if Gojou wins, and 'D' if the game ends in a draw. Do not print spaces between the characters in one line.

输入输出样例

输入样例 #1

3 1
1 2 4
6 8 3
9 5 7

输出样例 #1

GGG
MGG
MGG