algorithm - 与迷宫有关的游戏

Question

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.

注意:字符“.”代表可移动的土地，字符“#”代表障碍物!

我发布这个问题的目的是想尝试动态规划或递归来确定谁是这场比赛的赢家。

Answer 1

那么你可以申请Sprague-Grundy theorem找出获胜者。

所以计算粗糙的数字会是这样的:

1. 用 0 标记确定丢失的单元格(我们不能上升或离开的单元格)

0 . # 0 .
# . . . #
0 . # . .
# . . . .
0 . . . .

1. 循环遍历剩余的单元格，并针对每个未知单元格(标记为 .)一次找到所有可到达的单元格
2. 现在MEX这些单元格的值将是未知单元格
3. 填满所有单元格后，我们将得到如下内容:

0 1 # 0 1
# 0 1 2 #
0 2 # 1 0
# 3 0 4 1
0 4 1 3 2

1. 因此如果起始单元格 (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)，如下所示:

1. 因为我们一次只玩一个游戏板，所以我们真的不需要所有那些grundy numbers，知道当前cell是否有grundy number 0就足够了
2. 我们将那些具有 grundy 值 0 的单元格称为失败单元格，因此现在我们可以从单元格 (i,j) 中获胜，当且仅当我们可以移动到某个失败的单元格。
3. 如果我们为此使用 for/while 循环，搜索可到达的单元格仍将导致 O(n^3)
4. 要获得 O(n^2)，我们需要为行和列使用前缀数组。
5. so win[i][j] - 存储我们是否可以从单元格 (i,j) 中获胜
6. loseRow[i][j] - 如果我们在第 i 行中有任何丢失的单元格可以从单元格 (i,j) 到达，则存储
7. 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");
}