## ECOO '15 R2 P2 - So So

View as PDF

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 64M

Problem types

In the game of XOXO (pronounced So So) the player starts with a large grid that is filled with square tiles, each marked with either an X or an O. On each turn, the player can swap any two vertically or horizontally adjacent tiles as long as the swap produces a vertical or horizontal line of or more X's or or more O's. Any tiles involved in such a row are removed from the board. A single swap may produce multiple lines, in which case all the tiles that are part of one of the new lines are removed.

If you manage to remove all the tiles through repeated swapping like this, you have solved the board and you win the game.

The input will contain test cases. Each test case starts with two integers and on a single line separated by a space (, , ). These numbers indicate the number of rows and columns in each of the boards that follow. The next lines will contain different starting boards, one after another, each represented as rows of characters.

Each character will either be a capital X or a capital letter O (not zero) and there will be no horizontal or vertical lines of X's or O's greater than length anywhere on any starting board.

Your job is to determine whether or not it is possible to solve each board and then output an S (solvable) or an N (not solvable) for each board. The characters for each test case must appear on a single line with no spaces separating them. Note that the sample input below contains only test case, but the real data files will contain .

#### Sample Input

4 4
XXOX
OOXX
XXOO
XOXO
OOXO
OXXO
XOOX
OOXX
OOXO
XXOX
OXOO
OOXO
OOXX
XXOX
OXXO
XOXX
XOOX
OXOO
OOXO
XXOX

#### Sample Output

NSSSS

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

• commented on April 8, 2016, 1:40 a.m. edited

What happens to the space where there used to be tiles?

XRXX

(R for removed tile)

Are we allowed to go across the R?

• commented on April 8, 2016, 11:33 a.m.

No. The blank is left there as a placeholder and cannot be swapped with an adjacent tile.

• commented on April 9, 2016, 9:54 a.m.

Thank you :)