题目理解与转化

我们可以将这个问题抽象成一个在无向图上进行的组合游戏。

• 图的构建：棋盘的每一个非障碍格子（.）就是图中的一个顶点。如果两个非障碍格子相邻（上下左右），那么它们之间就存在一条无向边。
• 游戏规则：
  1. 起点：Alice 首先选择一个顶点作为起点，放下棋子。
  2. 轮流移动：Bob 先手，两人轮流将棋子沿着边移动到一个未被访问过的相邻顶点。
  3. 胜负判定：无法进行合法移动的玩家输掉游戏。

题目要求我们找出所有这样的起点：当 Alice 选择它后，无论 Bob 如何应对，Alice 都能保证获胜。

核心思路：博弈论与图的匹配

这个游戏是经典的无环有向图上的博弈（Impartial Combinatorial Games）的一个变种，可以用SG函数的理论来分析。但在这个特定规则下（棋盘是二分图，且移动路径不可重复），有一个更直观和强大的工具：匹配理论。

1. 二分图性质： 棋盘可以被看作一个二分图。我们可以像国际象棋棋盘一样进行黑白染色。例如，规定左上角 (1,1) 为黑色，那么与它相邻的格子就是白色，以此类推。在这样的染色下，每一步移动必然是从一种颜色的格子走到另一种颜色的格子。因此，整个游戏过程实际上是在一个二分图上进行。

2. 游戏本质： 这个游戏等价于在该二分图上进行的一场 “走边” 游戏。玩家从 Alice 选定的起点开始，轮流选择一条边移动，并且走过的边和点都不能再使用。这本质上是在这个二分图的一个连通分量上，寻找一条最长路径的问题。

3. 关键概念：最大匹配与必败点 在这种“不能重复访问”的路径游戏中，一个核心结论是：

   • 如果整个图（或者说包含起点的连通分量）存在一个最大匹配，使得起点不在这个最大匹配中（即起点是“非匹配点”），那么先手（在这个阶段是 Bob）就处于劣势，后手（Alice）有必胜策略。
   • 反之，如果起点被所有的最大匹配所包含（即起点是“匹配点”），那么先手（Bob）有必胜策略。

   直观解释：

   • 起点非匹配点：Bob 第一步必须从非匹配点走到一个匹配点（根据最大匹配的定义）。此后，Alice 总是可以沿着匹配边进行“镜像”操作。无论 Bob 怎么走，Alice 总能找到一条匹配边来回应。最终，Bob 会率先无路可走。Alice 作为后手，总能将胜利握在手中。
   • 起点是匹配点：Bob 第一步就可以沿着匹配边走到另一个点。此时，局面变成了 Bob 作为后手，而 Alice 变成了先手，并且 Bob 刚刚创造了一个对后手有利的局面（新的起点是非匹配点）。所以 Bob 可以复制上面 Alice 的策略来获胜。

结论与算法思想

因此，解题的步骤就非常清晰了：

1. 将棋盘构建成一个二分图，其中顶点是非障碍格子，边是相邻关系。
2. 使用算法（如匈牙利算法或基于最大流的算法）求出这个二分图的最大匹配。
3. 根据最大匹配，找出所有非匹配点。这些点就是 Alice 有必胜策略的初始位置。

为什么样例的输出是 (1,2) 和 (2,1)？ 在 2x2 的棋盘（障碍在 (1,1)）中，有效的格子是 (1,2), (2,1), (2,2)。这个二分图的最大匹配大小是 1（例如，可以匹配 (1,2) 和 (2,2)）。在这个匹配下，(2,1) 是非匹配点。如果我们换一个最大匹配（例如匹配 (2,1) 和 (2,2)），那么 (1,2) 就成了非匹配点。无论哪种最大匹配，(2,2) 总是被包含在某个最大匹配中，所以它是必败点。而 (1,2) 和 (2,1) 总有一个是非匹配点，所以它们都是必胜点。

总结

这道题巧妙地将一个棋盘上的路径游戏，通过二分图建模，转化为了一个寻找最大匹配中非匹配点的问题。它考察了对组合博弈论核心思想的理解，以及将具体问题抽象为经典图论模型的能力。解题的关键在于认识到：Alice 的必胜策略，等价于将棋子放在一个“非必需”的格子上，使得Bob无论第一步怎么走，都会将棋子送入一个Alice可以掌控的“对称”局面中。