与迷宫有关的游戏
A game relevant to maze
A和B进行如下游戏：
For maze represented by matrix has size n × n, the cell contains character "." represents the movable land and the cell contains character "#" character represents an obstacle that cannot be stepped on. Starting from the cell (n, n), each person takes turns choosing a next position to move. The new position must be on the left or upward the current cell (Move as the rook in the chess). There are no obstacles in the middle of the current position and the new location. If you can't find a new position, that person will lose. A is the one who go first. Determine who is the winner.
例如：
- n = 2 和迷宫：
. .
. .
结果是B，因为最初在坐标(2,2)，A会向左或向上，所以会有坐标(1,2)或(2,1)。然后B会移动到坐标（1,1）。 A不能动了，所以他输了，B赢了。
- 用 n = 5 和迷宫:
. . # . .
# . . . #
. . # . .
# . . . .
. . . . .
同理说明，A为胜
这是我的尝试：我尝试使用递归编程来确定谁是赢家，但是当n很大时花费的时间太长，我尝试构建这个问题的动态规划。
编辑：
So, the main of this problem to how we can determine who is the winner in this game. Suppose that initially at coordinates (n,n), we have a stone. A and B take turns playing a game as follows: A will choose a new position to move this stone (we can image that the stone like a rook in a chess), this new position must be on the left or above the current cell, after then B also choose a new position to move this stone. Until, the person who can't move this stone will be loser.
注意：字符“.”代表可移动的土地，字符“#”代表障碍物！
我的目的是 post 这个问题是我想尝试动态规划或递归来确定谁是这场比赛的赢家。
我们可以将矩阵中的坐标分类为 winning（即走棋的一方获胜，正确的玩法）或 losing（即移动正确的一方输了）。
可动地对应的坐标(r,c)为
- 如果没有合法的着法就输了；
- 如果所有合法移动都到达获胜坐标，则输；
- 如果至少有一个合法的移动失去坐标，则获胜。
请注意，根据第一条规则，(1,1) 输了，因此根据最后一条规则，谁能把石头移到 (1,1) 就赢了。
你的第二个矩阵的分类是：
L W # L W
# L W W #
L W # W L
# W L W W
L W W W W
由于坐标的值只取决于左边和上面的值，我们可以按top-to-bottom、left-to-right的顺序计算值。你真的不需要递归或动态编程。像
for r in 1...n
for c in 1...n
look left and up until the edge of the board or the first # sign
if there are any L values, then mark (r,c) as winning
otherwise mark (r,c) as losing
这种天真的方法每个坐标需要 O(n) 时间，所以总时间为 O(n3)。这可以通过在扫描矩阵时维护一些布尔标志来改进为 O(n2)：
- 一行标志表明我们是否可以从当前位置向左移动到亏损位置。 L 的值会将标志设置为真，而# 符号会将其重置为假。
- N 列标志，其中 fi 表示我们是否可以向上移动column i 到一个亏损的位置。每个标志都会如上所述更改值。
那么你可以申请 Sprague-Grundy theorem 来找出获胜者。
所以计算粗糙的数字会是这样的：
- 用 0 标记 sure-loss 个单元格（我们不能向上或向左的单元格）
0 . # 0 .
# . . . #
0 . # . .
# . . . .
0 . . . .
- 遍历剩余的单元格，并针对每个未知单元格（标记为
.）一次性找到所有可到达的单元格
- 现在这些单元格中的 MEX 将是未知单元格的值
- 填满所有单元格后，我们将得到如下内容：
0 1 # 0 1
# 0 1 2 #
0 2 # 1 0
# 3 0 4 1
0 4 1 3 2
- 因此如果起始单元格 (n,n) 不是 0，玩家将获胜
示例代码 (C++)，O(n^3)：
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<string>A = {
"..#..",
"#...#",
"..#..",
"#....",
"....."};
int n = A.size();
int Grundy[n][n]={};
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(A[i][j]!='#')
{
int can[2*n+1]={};
int left = j-1;
while(left>=0 && A[i][left]!='#')
{
can[Grundy[i][left]]++;
left--;
}
int up = i-1;
while(up>=0 && A[up][j]!='#')
{
can[Grundy[up][j]]++;
up--;
}
while(can[Grundy[i][j]])Grundy[i][j]++;
}
cout<<(Grundy[n-1][n-1] ? "Player 1 wins\n" : "Player 2 wins\n");
}
这导致 O(n^3) 的解决方案，但我们仍然可以优化为 O(n^2)，如下所示：
- 因为我们一次只玩一个游戏板，所以我们真的不需要所有那些grundy numbers，知道当前单元格是否可以到达grundy number 0就足够了
- 让我们将那些具有 grundy 值 0 的单元格称为丢失单元格，因此现在我们可以从单元格 (i,j) 中获胜当且仅当我们可以移动到某个丢失单元格时。
- 如果我们为此使用 for/while 循环，搜索可到达的单元格仍将导致 O(n^3)
- 要获得 O(n^2)，我们需要为行和列使用前缀数组。
- so
win[i][j] - 存储我们是否可以从单元格 (i,j) 中获胜
loseRow[i][j] - 如果我们在第 i 行中有任何丢失的单元格可以从单元格 (i,j)loseCol[i][j] - 如果我们在第 j 列中有任何丢失的单元格可以从单元格 (i,j)
示例代码 (C++)，O(n^2)：
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<string>A = {
"..#..",
"#...#",
"..#..",
"#....",
"....."};
int n = A.size();
int win[n][n]={};
int loseRow[n][n]={};
int loseCol[n][n]={};
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(A[i][j]!='#')
{
if(j-1>=0 && A[i][j-1]!='#')
{
win[i][j]|=loseRow[i][j-1];
loseRow[i][j]=loseRow[i][j-1];
}
if(i-1>=0 && A[i-1][j]!='#')
{
win[i][j]|=loseCol[i-1][j];
loseCol[i][j]=loseCol[i-1][j];
}
loseRow[i][j]|=!win[i][j];
loseCol[i][j]|=!win[i][j];
}
cout<<(win[n-1][n-1] ? "Player 1 wins\n" : "Player 2 wins\n");
}
A和B进行如下游戏：
For maze represented by matrix has size n × n, the cell contains character "." represents the movable land and the cell contains character "#" character represents an obstacle that cannot be stepped on. Starting from the cell (n, n), each person takes turns choosing a next position to move. The new position must be on the left or upward the current cell (Move as the rook in the chess). There are no obstacles in the middle of the current position and the new location. If you can't find a new position, that person will lose. A is the one who go first. Determine who is the winner.
例如：
- n = 2 和迷宫：
. .
. .
结果是B，因为最初在坐标(2,2)，A会向左或向上，所以会有坐标(1,2)或(2,1)。然后B会移动到坐标（1,1）。 A不能动了，所以他输了，B赢了。
- 用 n = 5 和迷宫:
. . # . .
# . . . #
. . # . .
# . . . .
. . . . .
同理说明，A为胜
这是我的尝试：我尝试使用递归编程来确定谁是赢家，但是当n很大时花费的时间太长，我尝试构建这个问题的动态规划。
编辑：
So, the main of this problem to how we can determine who is the winner in this game. Suppose that initially at coordinates (n,n), we have a stone. A and B take turns playing a game as follows: A will choose a new position to move this stone (we can image that the stone like a rook in a chess), this new position must be on the left or above the current cell, after then B also choose a new position to move this stone. Until, the person who can't move this stone will be loser.
注意：字符“.”代表可移动的土地，字符“#”代表障碍物！
我的目的是 post 这个问题是我想尝试动态规划或递归来确定谁是这场比赛的赢家。
我们可以将矩阵中的坐标分类为 winning（即走棋的一方获胜，正确的玩法）或 losing（即移动正确的一方输了）。
可动地对应的坐标(r,c)为
- 如果没有合法的着法就输了；
- 如果所有合法移动都到达获胜坐标，则输；
- 如果至少有一个合法的移动失去坐标，则获胜。
请注意，根据第一条规则，(1,1) 输了，因此根据最后一条规则，谁能把石头移到 (1,1) 就赢了。
你的第二个矩阵的分类是：
L W # L W
# L W W #
L W # W L
# W L W W
L W W W W
由于坐标的值只取决于左边和上面的值，我们可以按top-to-bottom、left-to-right的顺序计算值。你真的不需要递归或动态编程。像
for r in 1...n
for c in 1...n
look left and up until the edge of the board or the first # sign
if there are any L values, then mark (r,c) as winning
otherwise mark (r,c) as losing
这种天真的方法每个坐标需要 O(n) 时间，所以总时间为 O(n3)。这可以通过在扫描矩阵时维护一些布尔标志来改进为 O(n2)：
- 一行标志表明我们是否可以从当前位置向左移动到亏损位置。 L 的值会将标志设置为真，而# 符号会将其重置为假。
- N 列标志，其中 fi 表示我们是否可以向上移动column i 到一个亏损的位置。每个标志都会如上所述更改值。
那么你可以申请 Sprague-Grundy theorem 来找出获胜者。
所以计算粗糙的数字会是这样的：
- 用 0 标记 sure-loss 个单元格（我们不能向上或向左的单元格）
0 . # 0 .
# . . . #
0 . # . .
# . . . .
0 . . . .
- 遍历剩余的单元格，并针对每个未知单元格（标记为
.）一次性找到所有可到达的单元格 - 现在这些单元格中的 MEX 将是未知单元格的值
- 填满所有单元格后，我们将得到如下内容：
0 1 # 0 1
# 0 1 2 #
0 2 # 1 0
# 3 0 4 1
0 4 1 3 2
- 因此如果起始单元格 (n,n) 不是 0，玩家将获胜
示例代码 (C++)，O(n^3)：
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<string>A = {
"..#..",
"#...#",
"..#..",
"#....",
"....."};
int n = A.size();
int Grundy[n][n]={};
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(A[i][j]!='#')
{
int can[2*n+1]={};
int left = j-1;
while(left>=0 && A[i][left]!='#')
{
can[Grundy[i][left]]++;
left--;
}
int up = i-1;
while(up>=0 && A[up][j]!='#')
{
can[Grundy[up][j]]++;
up--;
}
while(can[Grundy[i][j]])Grundy[i][j]++;
}
cout<<(Grundy[n-1][n-1] ? "Player 1 wins\n" : "Player 2 wins\n");
}
这导致 O(n^3) 的解决方案，但我们仍然可以优化为 O(n^2)，如下所示：
- 因为我们一次只玩一个游戏板，所以我们真的不需要所有那些grundy numbers，知道当前单元格是否可以到达grundy number 0就足够了
- 让我们将那些具有 grundy 值 0 的单元格称为丢失单元格，因此现在我们可以从单元格 (i,j) 中获胜当且仅当我们可以移动到某个丢失单元格时。
- 如果我们为此使用 for/while 循环，搜索可到达的单元格仍将导致 O(n^3)
- 要获得 O(n^2)，我们需要为行和列使用前缀数组。
- so
win[i][j]- 存储我们是否可以从单元格 (i,j) 中获胜 loseRow[i][j]- 如果我们在第 i 行中有任何丢失的单元格可以从单元格 (i,j) 到达，则存储
loseCol[i][j]- 如果我们在第 j 列中有任何丢失的单元格可以从单元格 (i,j) 到达，则存储
示例代码 (C++)，O(n^2)：
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<string>A = {
"..#..",
"#...#",
"..#..",
"#....",
"....."};
int n = A.size();
int win[n][n]={};
int loseRow[n][n]={};
int loseCol[n][n]={};
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(A[i][j]!='#')
{
if(j-1>=0 && A[i][j-1]!='#')
{
win[i][j]|=loseRow[i][j-1];
loseRow[i][j]=loseRow[i][j-1];
}
if(i-1>=0 && A[i-1][j]!='#')
{
win[i][j]|=loseCol[i-1][j];
loseCol[i][j]=loseCol[i-1][j];
}
loseRow[i][j]|=!win[i][j];
loseCol[i][j]|=!win[i][j];
}
cout<<(win[n-1][n-1] ? "Player 1 wins\n" : "Player 2 wins\n");
}