A grid game P57928
Consider a two-player game, played on an r × c grid, where every cell is initially permitted. Alternating moves, each player chooses any permitted cell x, and marks as forbidden x, all the cells of the same row to the left and to the right of x, and all the cells of the same column above and below x, until an already forbidden cell or the border of the grid is found in every direction. The player that eventually cannot make any move loses the game.
Assume (1, 1) to be the upper-left cell. This is the result of the moves (3, 4), (5, 2) and (1, 1) in this order on a grid 5 × 6 (forbidden cells are painted grey):
linewidth=0.5pt
[fillstyle=solid,fillcolor=gray](16,04)(28,06) [fillstyle=solid,fillcolor=gray](22,00)(24,10)
[fillstyle=solid,fillcolor=gray](32,04)(44,06) [fillstyle=solid,fillcolor=gray](38,00)(40,10)
[fillstyle=solid,fillcolor=gray](32,00)(38,02) [fillstyle=solid,fillcolor=gray](34,02)(36,04)
[fillstyle=solid,fillcolor=gray](48,04)(60,06) [fillstyle=solid,fillcolor=gray](54,00)(56,10)
[fillstyle=solid,fillcolor=gray](48,00)(54,02) [fillstyle=solid,fillcolor=gray](50,02)(52,04)
[fillstyle=solid,fillcolor=gray](48,08)(54,10) [fillstyle=solid,fillcolor=gray](48,06)(50,08)
(00,00)(00,10) (02,00)(02,10) (04,00)(04,10) (06,00)(06,10) (08,00)(08,10) (10,00)(10,10) (12,00)(12,10) (00,00)(12,00) (00,02)(12,02) (00,04)(12,04) (00,06)(12,06) (00,08)(12,08) (00,10)(12,10)
(16,00)(16,10) (18,00)(18,10) (20,00)(20,10) (22,00)(22,10) (24,00)(24,10) (26,00)(26,10) (28,00)(28,10) (16,00)(28,00) (16,02)(28,02) (16,04)(28,04) (16,06)(28,06) (16,08)(28,08) (16,10)(28,10)
(32,00)(32,10) (34,00)(34,10) (36,00)(36,10) (38,00)(38,10) (40,00)(40,10) (42,00)(42,10) (44,00)(44,10) (32,00)(44,00) (32,02)(44,02) (32,04)(44,04) (32,06)(44,06) (32,08)(44,08) (32,10)(44,10)
(48,00)(48,10) (50,00)(50,10) (52,00)(52,10) (54,00)(54,10) (56,00)(56,10) (58,00)(58,10) (60,00)(60,10) (48,00)(60,00) (48,02)(60,02) (48,04)(60,04) (48,06)(60,06) (48,08)(60,08) (48,10)(60,10)
linewidth=1pt
(23,00)(23,04) (23,06)(23,10) (16,05)(22,05) (24,05)(28,05)
(39,00)(39,04) (39,06)(39,10) (32,05)(38,05) (40,05)(44,05)
(55,00)(55,04) (55,06)(55,10) (48,05)(54,05) (56,05)(60,05)
(35,02)(35,04) (32,01)(34,01) (36,01)(38,01)
(51,02)(51,04) (48,01)(50,01) (52,01)(54,01)
(50,09)(54,09) (49,08)(49,06)
linewidth=2pt
(22,04)(24,06) (24,04)(22,06)
(38,04)(40,06) (40,04)(38,06)
(54,04)(56,06) (56,04)(54,06)
(34,02)(36,00) (36,02)(34,00)
(50,02)(52,00) (52,02)(50,00)
(48,08)(50,10) (50,08)(48,10)
The game after the moves (3, 4) and (5, 2) is winning, that is, with perfect play the oponent is doomed to lose. But it is easy to see that the game after (1, 1) is also winning, which implies that (1, 1) was a bad move for this position.
Write a program that, for every given partial game, tells if it is winning or losing.
Input
Input consists of several cases. Each case begins with r and c, followed by a number m, followed by m moves. Assume 1 ≤ r, c ≤ 80, and that each sequence of moves is correct.
Output
For every case, print “winning” or “losing”.
Input
5 6 0 5 6 1 3 4 5 6 2 3 4 5 2 5 6 3 3 4 5 2 1 1 6 6 1 6 5 6 6 0 12 8 0 80 80 0
Output
winning losing winning winning losing winning losing winning
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++