valeriikozlov

silent_1991, Алгоритм решения у меня такой (я привожу доску не бесконечную а 8*8, но все будет понятно):
Клетки обозначенные 0 - это клетки неизвестные (неизвестно, кто победит если с них начать). Клетка с координатами 0 0 - это клетка нижняя левая.
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Т.к. всегда начинает 1 игрок, то логично предположить:
1 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0
1 0 0 0 0 1 0 0
1 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
1 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1
Т.е. все клетки обозначенные 1 - это клетки из которых если начать, то выигрывает 1 игрок.
Теперь обращаем внимание на клетки с координатами (3,2) и (2,3) - Если первый игрок начинает ходить с этих клеток, то он сможет пойти только на те клетки где выигрывает "первый начинающий ходить" игрок. В данном случае после его хода, "первым начинающим ходить" будет второй. Т.е. клетки (3,2) и (2,3) - это клетки выигрышные для второго игрока. Получаем:
1 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0
1 0 0 0 0 1 0 0
1 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
1 2 1 0 0 0 0 0
1 1 2 0 0 0 0 0
1 1 1 1 1 1 1 1
(Еще раз повторюсь, что начинает всегда ходить 1 игрок. А 1 на поле означает что из этой клетки если начинается игра выиграет 1 игрок. А 2 на поле означает, что из этой клетки если начинается игра выиграет 2 игрок)
Теперь рассмотрим клетки (пока неизвестные) вертикальные, горизонтальные и по диагонали к полученным 2-кам. Если игра начинается из них, то выигает всегда 1 игрок. При правильной игре 1 игрок всегда сделает ход в клетку с 2-кой (тем самым обрекает противника на поражение). Значит имеем:
1 1 1 0 0 0 1 1
1 1 1 0 0 1 1 1
1 1 1 0 1 1 1 0
1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 0
1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1
1 1 1 1 1 1 1 1
Следующие на рассмотрении клетки (6,4) (4,6) (пока неизвестные)
Если первый игрок начинает ходить из этих клеток, то из них он может попасть только в клетки, в которых выигрывает только "первый начинающий ходить". В данном случае это будет игрок 2.
Значит получаем:
1 1 1 0 0 0 1 1
1 1 1 0 0 1 1 1
1 1 1 2 1 1 1 0
1 1 1 1 1 1 0 0
1 1 1 1 1 2 0 0
1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1
1 1 1 1 1 1 1 1
Затем снова заполняем (пока неизвестные) вертикальные, горизонтальные и по диагонали к полученным 2-кам, единицами (выше сказано почему):
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 2 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 2 1 1
1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1
1 1 1 1 1 1 1 1
Следующие на рассмотрении точки с координатами (8,5) и (5,8) - там значения равны 2.
и т.д.
Значения: (1 <= M, N <= 250) не такие уж и большие. Все заполнение матрицы пройдет быстро.

Вернуться к обсуждению:
Задачи для тренировки и лучшего понимания

3