시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 17 | 7 | 7 | 43.750% |
It is 1990 and you are in the development team of a video game that is going to revolutionize the future of arcades. The player is given a rectangular board with some white and black squares. The goal is to turn the whole board white. At each turn, the player may choose a tetromino from an infinite supply, move and rotate it within the limits of the board, and toggle the colour of the four squares covered by the tetromino. A tetromino is a connected set of 4 squares (see Figure D.1).
Unfortunately, the testing team has been complaining about some levels being impossible to solve. You know that testers are skilled enough to place a piece in any position and rotation needed, so the problem may be somewhere else. Your next debugging step is to write a program that checks whether a level is solvable.
Figure D.1: All tetrominoes. From Wikimedia.
The first line contains two integers m and n (1 ≤ m, n ≤ 100), the dimensions of the board. m lines with n characters each follow. The character ‘.’ represents a white square, and the character ‘X’ represents a black square.
One line with the word “possible” if the level is solvable and “impossible” if it is not.
3 3 ... ... ...
possible
3 3 XXX XXX XXX
impossible
Contest > KTH Challenge > KTH Challenge 2015 D번