Воспользуемся методом динамического программирование с запоминанием: пусть d[А][В] - выиграет ли игрок, если он ходит фишкой в позиции A, а у второго игрока фишка в позиции B. Перебираем следующий ход и смотрим - если был хоть один ход в проигрышное состояние, то наше состояние выигрышное, иначе проигрышное.
Код тут: http://ideone.com/IvaJy
O(N * N * 2K)
Страницы 1