시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB209945.000%

문제

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.

예제 입력 1

3 3
...
...
...

예제 출력 1

possible

예제 입력 2

3 3
XXX
XXX
XXX

예제 출력 2

impossible

출처

Contest > KTH Challenge > KTH Challenge 2015 D번

  • 문제를 만든 사람: Marc Vinyals