Перемещение по сетке

Опубликовано: 19 Сентября, 2022

Дана сетка на плоскости XY с размерами rxc (где r обозначает максимальное количество ячеек по оси X , а c обозначает максимальное количество ячеек по оси Y ), два игрока (скажем, ДЖОН и АРЬЯ) могут перемещать монету по сетке, удовлетворяя следующим условиям: правила:

  • Изначально на ячейке (1, 1) лежит монета.
  • ДЖОН будет двигаться первым.
  • Оба будут играть по очереди.
  • На каждом ходу они могут размещать монету в следующих позициях, если текущая позиция монеты равна x, y.
  • (x+1, y), (x+2, y), (x+3, y), (x, y+1), (x, y+2), (x, y+3), (x , у+4), (х, у+5), (х, у+6)
  • Они не могут выйти за пределы сети.
  • Игрок, который не может сделать ни одного хода, проигрывает эту игру.
  • Оба играют оптимально.

Примеры:

Input: r = 1, c = 2
Output: JON 
Explanation: ARYA lost the game because
he won’t able to move after JON’s move. 

Input: r = 2, c = 2
Output: ARYA
Explanation: After first move by JON (1, 2 or 2, 1)
and second move by ARYA(2, 2) JON won’t able to
move so ARYA wins. 

Подход: Эту проблему можно решить с помощью теории игр, основанной на следующей идее:

Check the following points:

  • For rows whoever leaves 4 cells to be covered wins the game and for columns, whoever leaves 7 cells to be covered, wins the game.
  • To win the game one has to make sure that the opponent cannot win either row or column i.e. he can win both the row and column and leaves 4 cells in row and 7 cells in columns.
  • The game starts with Jon. So if (r-1)%7 = (c-1)%4, then Jon can win either row or column but not both. So Arya wins that game.
  • In all other cases Jon wins the game.

Следуйте инструкциям, чтобы решить проблему:

  • Получите значение (r-1)%7 и (c-1)%4 .
  • Если эти два значения совпадают, то выигрывает Арья.
  • В противном случае Джон побеждает.

Ниже приведена реализация вышеуказанного подхода:

Сложность времени: О(1)
Вспомогательное пространство: О(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ