#P15195. [SWERC 2019] River Game

[SWERC 2019] River Game

说明

你和一位鸟类学家朋友正在湿地中花费数小时观鸟,等待一只你想拍照的稀有鸟类。

为了消磨时间,你们设计了一个小游戏。湿地用一个 N×NN \times N 的网格表示,网格由三种类型的方格组成:坚实地面、潮湿区域和受保护区域。

相连的潮湿区域方格形成潮湿区域。潮湿区域是潮湿区域方格的最大集合,使得我们可以通过相连的潮湿区域方格路径从区域中的任意方格走到区域中的任意其他方格。两个方格当共享一条边时被认为是相连的,因此不在网格边界的方格与另外 4 个方格相连。每个潮湿区域必须与网格的左侧和右侧都相连,且包含的潮湿区域方格不超过 2N2N 个。属于两个不同潮湿区域的两个潮湿区域方格之间的距离至少为 3,距离通过在网格上水平或垂直移动来计算。例如,在下面的两个例子中,蓝色方格彼此之间的距离为 3。

:::align{center} :::

你和你的朋友将轮流在湿地上放置相机,规则如下:

  • 相机必须放在坚实地面方格上。
  • 相机必须与一个潮湿区域方格相邻,以便你能拍摄鸟类照片。
  • 相机不能放在受保护区域方格上。
  • 不能有两个相机放在同一方格上。
  • 相邻于同一潮湿区域的两个相机不能彼此相邻(再次强调,相邻是指共享一条边)。

第一个无法再放置相机的玩家输掉游戏。

假设双方都采取最优策略,先手玩家会赢还是会输?

输入格式

输入包含以下行:

  • 第一行,整数 NN
  • 接下来的 NN 行,每行一个字符串表示网格的一行:* 表示潮湿区域方格,. 表示坚实地面方格,x 表示受保护方格。

输出格式

如果双方都采取最优策略时先手玩家获胜,则输出四个单词 First player will win;否则输出 Second player will win

3
...
...
***
First player will win
10
**********
*.x.*.....
*...*.....
*****.....
..........
..........
xx******..
***x...*..
..*...x*.x
..********
Second player will win

提示

数据范围

输入满足 1N101 \leq N \leq 10

翻译由 DeepSeek 完成