A grid game P57928


Statement
 

pdf   zip

html

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):



unit=0.25cm (60,10)

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”.

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Semifinal
    Date
    2011-06-29