Pull to refresh

Тримино

Reading time 4 min
Views 3.7K
Привет, %usename%!
В этой статье я хочу немного рассказать про комбинаторные игры и разобрать решение одной из них. В жизни мы встречаемся именно с этим типом игр, формальное их определение звучит так:
Комбинаторная игра — это множество игровых позиций, про каждую из которых игрокам известно, как (в какие другие позиции) может ходить каждый из них.
Сегодня мы попытаемся понять суть подхода к простейшим играм, с этой целью рассмотрим игру «Тримино», которая заключается в следующем: имеется игровое поле размера 2*N, N <= 800 и бесконечное количество плоских фигурок, состоящих из трех клеточек (см.рисунок). Два игрока ходят по очереди, пусть первый из них Х, а второй Y. На каждом ходе игрок кладет фигурку, поворачивая ее как угодно, на свободное место. Накладывать фигурки друг на друга нельзя. Проигрывает тот кто не может сделать ход. Наша задача состоит в том чтобы опеределить кто победит при оптимальной игре: Х или Y.
Легко видеть что наша игра с нормальным окончанием (проигрывает тот кто не может ходить) и обладает свойствами комбинаторных игр, значит её можно свести к игре «Ним», что мы и попытаемся сделать. Общий подход к подобного рода задачам заключается в том чтобы разбивать большую игру на множество типичных, но меньшего размера, для каждой из них вычислять nim value через сумму игр, потом найти mex(minimal exclusive) всех разбиений и сравнить его с нулем. В случае равенства получаем P позицию, иначе N позицию. Все было бы тривиально, но в нашей игре есть некоторые небольшие трудности, которые, немного подумав, можно обойти. А трудность вот в чем: первоначальное поле имеет форму прямоугольника, но поставив первую триминошку мы разбиваем игру на две другие, одна из которых точно такая же, а другая отличается тем что один из ее краев кривой. Поэтому в нашей задаче ничего другого не остается, как сделать несколько типов игр, их будет 4: I, II, III, IV. Схематически они изображены на картинке.

Каждый из этих типов мы будем рассматривать отдельно, ставя триминошку в любые позиции и разбивая на суммы других игр. Теперь нужно проследить на какие игры можно разбить каждый из наших типов. Первый тип разбивается на сумму первого и второго, как бы мы не поворачивали фигурку, второй можно разбить на две вторых игры или на первую и третью. Третья разбивается на вторую и третью, четвертая тоже на вторую и третью. Симметричные варианты мы считаем одинаковыми так как они тождественны и на mex не повлияют, тем самым мы замечаем что третий и четвертый варианты абсолютно одинаковы, значит мы можем обойтись только одним из них, тем самым сократив нашу задачу. На рисунке ниже показаны способы разбиения:
  
Учитывая сделанные замечания и аккуратно расставляя триминошки напишем три рекурсивные функции с запоминанием на языке java.
Copy Source | Copy HTML
  1. private static int M = 800;
  2. private static int[] I = new int[M+1],
  3. II = new int[M+1],III = new int[M+1];
  4. static {
  5.     Arrays.fill(I, -1);
  6.     Arrays.fill(II, -1);
  7.     Arrays.fill(III, -1);
  8. }
  9.  
  10. private static int I(int n) {
  11.     if (I[n] >=  0) return I[n];
  12.     if (n ==  0 || n == 1) return I[n] =  0;
  13.     boolean[] mex = new boolean[M+1];
  14.     for (int i=1; i<n; i++)
  15.         mex[I(i - 1) ^ II(n - i)] = true;
  16.     for (int i= 0; i<=M; i++)
  17.         if (!mex[i]) return I[n] = i;
  18.     return I[n] = M+1;
  19. }
  20.  
  21. private static int II(int n) {
  22.     if (II[n] >=  0) return II[n];
  23.     if (n ==  0 || n == 1) return II[n] =  0;
  24.     boolean[] mex = new boolean[M+1];
  25.     for (int i=2; i<n; i++)
  26.         mex[II(i - 1) ^ II(n - i)] = true;
  27.     for (int i=2; i<=n; i++)
  28.         mex[III(i - 1) ^ I(n - i)] = true;
  29.     for (int i= 0; i<=M; i++)
  30.         if (!mex[i]) return II[n] = i;
  31.     return II[n] = M+1;
  32. }
  33.  
  34. private static int III(int n) {
  35.     if (III[n] >=  0) return III[n];
  36.     if (n ==  0 || n == 1) return III[n] =  0;
  37.     boolean[] mex = new boolean[M+1];
  38.     for (int i=2; i<n; i++)
  39.         mex[III(i - 1) ^ II(n - i)] = true;
  40.     for (int i= 0; i<=M; i++)
  41.         if (!mex[i]) return III[n] = i;
  42.     return III[n] = M+1;
  43. }
  44.  


Теперь осталось только выдать наш ответ:
Copy Source | Copy HTML
  1. int n = nextInt();
  2. out.println(I(n) ==  0 ? 'Y' : 'X');


В разборе этой задачи я старался показать общий стиль мышления, он практически однотипен в решениях подобных задач. Разобранная выше задача взята из архива SPOJ и доступна по ссылке TRIOMINO.

Спасибо за внимание.
Tags:
Hubs:
+19
Comments 23
Comments Comments 23

Articles