Игра, относящаяся к лабиринту - PullRequest
Новая
       19

Игра, относящаяся к лабиринту

2 голосов
/ 08 мая 2019

A и B играют в игру следующим образом:

Для лабиринта, представленного матрицей, имеет размер n × n , ячейка содержит символ "."представляет подвижную землю, а ячейка содержит символ «#», символ представляет собой препятствие, на которое нельзя ступить.Начиная с ячейки ( n , n ), каждый человек по очереди выбирает следующую позицию для перемещения.Новая позиция должна быть слева или вверх по текущей ячейке (двигаться как ладья в шахматах).Нет никаких препятствий в середине текущей позиции и новой локации.Если вы не можете найти новую должность, этот человек проиграет.А тот, кто идет первым.Определите, кто является победителем.

Например:

  • С n = 2 и лабиринт: 
 . .
 . .

Результат - B, потому что первоначально в координатах (2,2), A пойдет влево или вверх, поэтому будут координаты (1,2) или (2,1).Тогда B переместится в координаты (1,1).A больше не может двигаться, поэтому он проигрывает и выигрывает B.

  • С n = 5 и лабиринтом: 
. . # . .
# . . . #
. . # . .
# . . . .
. . . . .

Объясняя аналогично, у нас будет А. будет победителем.

Это моя попытка: я пытался использовать рекурсивное программирование, чтобы определить, кто является победителем, но это занимает слишком много времени, когда n велико, иЯ пытался построить динамическое программирование для этой проблемы.

Редактировать:

Итак, основная проблема в том, как мы можем определить, кто является победителем в этой игре.Предположим, что изначально в координатах ( n , n ) у нас есть камень.А и В по очереди играют в игру следующим образом: А выберет новую позицию, чтобы переместить этот камень (мы можем представить, что камень похож на ладью в шахматах), эта новая позиция должна быть слева или над текущей ячейкой,после этого B также выберите новую позицию, чтобы переместить этот камень.До тех пор, пока человек, который не сможет сдвинуть этот камень, будет неудачником.

Обратите внимание: символ "."представляет собой подвижную землю, а символ "#" представляет собой препятствие!

И моя цель при публикации этой проблемы - я хочу попробовать динамическое программирование или рекурсию, чтобы определить, кто победит в этой игре.

Ответы [ 2 ]

2 голосов
/ 08 мая 2019

Ну, вы можете просто применить Теорема Спрейга-Гранди , чтобы узнать победителя.

Таким образом, вычисление чисел Гранди будет выглядеть примерно так:

  1. МаркЯчейки без потерь с 0 (ячейки, в которых мы не можем идти вверх или влево) 
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) следующим образом:

  1. Поскольку мы играем только на одной игровой доске за раз, мы не можемдействительно нужны все эти цифры, достаточно знать, доступно ли число 0 для текущей ячейки
  2. Давайте назовем эти ячейки с нулевой величиной 0 потерянными, так что теперь мы можем выиграть из ячейки (i, j) тогда и только тогда, когда мы сможем перейти к какой-то убывающей ячейке.
  3. поиск доступных достижимых ячеек все равно приведет к O (n ^ 3), если мы используем цикл for / while для этого
  4. .O (n ^ 2) нам нужно использовать префиксные массивы для строк и столбцов.
  5. , поэтому win[i][j] - хранит, можем ли мы выиграть из ячейки (i, j)
  6. loseRow[i][j] -сохраняет, если у нас есть какие-либо убыточные ячейки в строке i, которые могут быть достигнуты из ячейки (i, j)
  7. loseCol[i][j] - сохраняет, если у нас есть какие-либо потерянные ячейки в столбце j, которые могут быть достигнуты из ячейки (i,к)

Пример кода (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");
}
2 голосов
/ 08 мая 2019

Мы можем классифицировать координаты в матрице как выигрыш (т. Е. Сторона, которая движется, выигрывает при правильной игре) или проигрыш (т. Е. Сторона, которая движется, проигрывает при правильной игре).

Координата (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

Поскольку значение координаты зависит только от значений слева и сверху, мы можем вычислять значения сверху вниз, слева направо. Вам не нужно рекурсия или динамическое программирование. Что-то вроде 

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 (n 3 ) общего времени. Это можно улучшить до O (n 2 ), поддерживая некоторые логические флаги при сканировании матрицы:

  • Флаг одной строки, указывающий, можем ли мы сделать перемещение влево от текущей позиции к проигрышной. Значение L установит для флага значение true, а для знака # будет установлено значение false.
  • N флаги столбцов, где f i указывает, можем ли мы сделать движение вверх по столбцу i в проигрышную позицию. Каждый флаг меняет значения, как описано выше.
...