ECOO '15 R2 P2 - So So

View as PDF
Submit solution
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 3 or more X's or 3 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 10 test cases. Each test case starts with two integers R and C on a single line separated by a space (R > 0, C > 0, R \times C \le 30). These numbers indicate the number of rows and columns in each of the boards that follow. The next 5 \times R lines will contain 5 different starting boards, one after another, each represented as R rows of C 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 2 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 5 characters for each test case must appear on a single line with no spaces separating them. Note that the sample input below contains only 1 test case, but the real data files will contain 10.

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

Comments


  • 0
    Zander  commented on April 8, 2016, 5: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?


    • 4
      Phoenix1369  commented on April 8, 2016, 3:33 p.m.

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


      • 0
        Zander  commented on April 9, 2016, 1:54 p.m.

        Thank you :)