P14722 [ICPC 2022 Seoul R] Card Game

Alice 和 Bob 玩一个轮流从网格棋盘上取走卡片的游戏。游戏开始时，一个 $N \times M$ 大小的网格棋盘的每个单元格中有一张卡片，每张卡片被涂成三种颜色之一：红色、蓝色或绿色。在网格中，左上角单元格的位置用 $(1,1)$ 表示，右下角单元格的位置用 $(N,M)$ 表示。 Alice 和 Bob 从放置在网格上的卡片中选择一张，然后根据以下规则移除卡片。 - 如果所选卡片的颜色是**红色**，则移除所有以其为基础、位于斜率为 $1$ 的对角线上的“连通卡片”。 - 如果所选卡片的颜色是**蓝色**，则移除所有以其为基础、位于斜率为 $-1$ 的对角线上的“连通卡片”。 - 如果所选卡片的颜色是**绿色**，则移除所有以其为基础、位于两个方向对角线上的“连通卡片”。 所选卡片的“连通卡片”是指沿着斜率为 $1$ 或 $-1$ 的对角线、包括所选卡片在内的连续相邻卡片。 例如，当游戏进行时的当前棋盘状态如图 A.1 所示时，设所选卡片是放置在 $(4,3)$ 的红色卡片。如图 A.1 所示，位于斜率为 $1$ 的对角线上的“连通卡片”指的是放置在椭圆形圆圈中的卡片，它们应该被移除。也就是说，从位置 $(4,3)$ 沿对角线向两个方向移动时，移动路径上的单元格中放置的卡片是“连通卡片”。然而，沿着所选单元格 $(4,3)$ 的对角线向两个方向移动时，如果遇到网格边界或空白单元格，移动就会停止。 :::align{center}  图 A.1. 说明 $(4, 3)$ 处红色卡片连通卡片的示例 ::: 类似地，当游戏进行时的当前棋盘状态如图 A.2 所示时，设所选卡片是放置在 $(3,5)$ 的蓝色卡片。如图 A.2 所示，位于斜率为 $-1$ 的对角线上的“连通卡片”指的是放置在椭圆形圆圈中的卡片，它们应该被移除。 :::align{center}  图 A.2. 说明 $(3, 5)$ 处蓝色卡片连通卡片的示例 ::: 图 A.3 显示了当所选卡片是放置在 $(4,5)$ 的绿色卡片时，要被移除的卡片。 :::align{center}  图 A.3. 说明 $(4, 5)$ 处绿色卡片连通卡片的示例 ::: Alice 和 Bob 轮流从网格中选择一张卡片，并根据所选卡片的颜色，按照上述规则移除“连通卡片”。谁移走最后一张卡片，谁就赢得游戏。也就是说，当网格上没有卡片可供选择而无法移除任何卡片的玩家输掉游戏。Alice 和 Bob 都深知如何赢得游戏的策略，并尽最大努力争取胜利。 给定网格棋盘的大小以及放置在棋盘上的卡片颜色信息，请编写一个程序来判断当 Alice 先手时，她是否能赢。

你的程序需要从标准输入读取数据。输入的第一行包含两个整数 $N$ 和 $M$ ($1 \leq N, M \leq 25$)，其中 $N$ 是网格的行数，$M$ 是列数。接下来的 $N$ 行中，第 $i$ 行包含一个长度为 $M$ 的字符串，表示网格中第 $i$ 行 $M$ 张卡片的颜色。字符串中的每个字符是 ‘R’、‘B’ 或 ‘G’，分别代表红色、蓝色或绿色。

你的程序需要向标准输出写入数据。输出恰好一行。该行应包含一个大写字母：如果 Alice 获胜则输出 ‘W’，如果 Alice 失败则输出 ‘L’。

翻译由 DeepSeek V3 完成