IOIQR P5 - Some Game

View as PDF

Submit solution

Points: 25
Time limit: 4.2s
Memory limit: 256M

Author:
Problem type
April Fools Contest, 2017

Some Game is a popular game played amongst a group of people. In this adaption of Some Game, N new players will make some moves upon an H by W board. Every square initially contains a 0. Player 1 makes the first move. After this move, player 2 makes the second move. This goes on until the final player (with number N) has made a move. Afterwards, player 1 can move again. A move consists of player i putting i on any square with label 0.

Some Game will end when one player forms a row, column, diagonal or knight hop with a length of K or greater, containing only that player's number. If there are ties, the lowest number player wins. To make the board seem infinite, the players have glued the left and right ends of the board together (like a cylinder). Also, they have glued the top and bottom edges of the board together. Some Game will still end if the winning sequence goes across the glue.

Some Game will also end when there are no more valid moves. Moves are not permitted after Some Game ends.

For reference, a knight hop will be shown below. The initial square is A, and paths from A to any B are knight hops.

.......
..B.B..
.B...B.
...A...
.B...B.
..B.B..
.......

In the next few cases, . are unimportant squares, and 1 are squares with label 1.

 A     B     C      D
1..   1..   ...   .....
.1.   ...   1.1   .1...
..1   .1.   ...   .....
                  ..1..
                  ....1

In example A, player 1 will win if K is 3, or 4, or so on.

In example B, player 1 will win if K is 2.

In example C, player 1 will win if K is 2.

In example D, player 1 will win if K is 2. Note that knight hops must continue in the same direction, so if K is 3 or greater, player 1 would not win.

The standard input stream contains 10 sets of data. In every test case/set of data, the players have gotten tired and have simultaneously quit (Some Game is very tiring). You will work with arbitrary boards of Some Game, plus some extra info. Line 1 contains the extra info, which are N, W, H, and K in this arrangement, and are also integers. There are N players playing Some Game (1 \le N \le 9001). H and W are defined above (1 \le H, W \le 420). The winning threshold, K (0 \le K \le 9001), is non-negative. The next H lines of input each contain W integers. Every integer on these H lines will be between 0 and N inclusive, and represents the state of the square on the board when the players have quit. If the Some Game game is still ongoing, or the board is full without a winner, print NO WINNERS. If player <x> has won, print PLAYER <x>, where <x> is an integer in the range 1 \dots N. If the state of the board is impossible, print ERROR. Make sure to print an empty line between each line of output. Your task is to read this data and print the correct lines of output.

Sample Input

The sample input contains 4 sets of data.

1 3 3 4
1 0 0
0 1 0
0 0 1
1 3 3 2
1 0 0
0 0 0
0 1 0
2 3 3 2
2 2 2
1 0 1
0 0 0
2 5 5 3
0 0 0 2 0
0 1 0 0 0
0 0 2 0 0
2 0 1 0 0
0 0 0 0 1

Sample Output

PLAYER 1

PLAYER 1

ERROR

NO WINNERS

Comments

There are no comments at the moment.