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
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~.
4 4 XXOX OOXX XXOO XOXO OOXO OXXO XOOX OOXX OOXO XXOX OXOO OOXO OOXX XXOX OXXO XOXX XOOX OXOO OOXO XXOX
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org