game
The game board of a very popular Internet game consists of a rectangular area divided into cells, organized in M lines and N columns. Lines are numbered from 1 to M, starting with the top line, and columns are numbered from 1 to N, starting with the left column.
Each cell contains a game piece of a specific color. Colors are coded using English capital letters.
The purpose of the game is to obtain groups of at least 3 same color pieces. A group is comprised of at least three same color pieces located on adjacent cells on the same line or on the same column. In the following image R colored pieces form a 4-piece group, V colored pieces form a 3-piece group, but pieces color A DON'T form any group:
|
T
|
B
|
C
|
C
|
E
|
F
|
G
|
H
|
|
V
|
N
|
R
|
R
|
R
|
R
|
U
|
P
|
|
V
|
X
|
A
|
B
|
C
|
D
|
E
|
L
|
|
V
|
A
|
A
|
M
|
N
|
U
|
P
|
T
|
Two types of moves are permitted
for creating groups of pieces:
1. Selecting a table line and circularly permuting a number of positions to
the right, with the pieces going out the right side of the table being moved
to the beginning of the line. E.g. for the following table configuration:
ABAD
BADC
ABCD
permuting line
two one position to the right results in configuration:
ABAD
CBAD
ABCD
and thus we have
two groups of three pieces each (one on column two and one on column
four)
2. Likewise we can select a table column which can be permuted down a number of positions, with the pieces going out the bottom being moved up to the beginning of said column.
A move is allowed only if it results in at least one group of pieces being eliminated.
Two moves are considered different if they don't involve the same line or the same column, or if they do, if the number of positions circularly permuted differs.
Task
a) Determine the number of first move possibilities for a given game board.
b) Determine the maximum number of pieces that can be eliminated after the first move, number which is equal to the sum of the number of pieces of all groups being formed as a result of said move.
c) Determine the first move to be executed so that the number of pieces that can be eliminated be maximum. If there is more than one solution the one that allows for permuting line one is preferred. If there is still more than one solution the option that has the minimum line index will be selected, and for the same line, the one with the minimum number of permuted positions.
Input Data
Line one of input file game.in contains two positive integers, M and N, separated by a single space, representing the number of lines and columns of the game board. Each of the following M lines contains N capital English letters, representing the colors of the game board pieces.
Output Data
The input file game.out
will contain on the first line a single positive integer representing the number
of first move possibilities. Line two of the file will contain a single positive
integer representing the maximum number of pieces that can be eliminated after
the first move. Line three contains a move that leads to the elimination of
a maximum number of pieces off the game board. A move is encoded using three
positive integers, x,
y, z,
separated by a space and having the following meaning:
- x is 1 if a line is being permuted and 2 if a column is being permuted;
- y represents the number of the line or column being permuted;
- z represents the number of positions of the circular permutation.
Constraints
Example
| game.in | game.out | game.in | game.out |
| 3 4 DBAD AADA DBCA |
4 6 1 2 2 |
3 4 ABAD BADC ABCA |
3 3 1 2 1 |
Time limit: 0.2 seconds/test
prof. Popescu Carmen
"Gheorghe Lazar" Sibiu National High School
Contact: carmen_cngl@yahoo.com