0231. Black-White King Strikes Back

Имя входного файла:	king.in
Имя выходного файла:	king.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

An irrecoverable event happened today's morning in the Chess World. Black King was killed. Of course, a letter about it was immediately sent to his old ally, White King. Frightened witnesses said that injuries on the King's body appeared from nothing. Axes began to move themselves and stroke King. After all, a strange force raised him up and threw down from a palace balcony mortally.

After White King had knew about it, he began to feel real danger. He understood that it's an awful deed of invisible Black-White King, who was considered dead after a legendary year, when Black and White King united to catch Black-White King, after what he was brutally hanged.

The danger seemed to be over, and Kings got back to their kingdoms and returned to their basic life. But now White King needs to defend his life without Black King. Fortunately, when Black King was still alive, he created a new chess piece, Guardian. This awful piece is always attacking all neighboring cells and a cell under itself, even if it's nothing (seen) in this cell (of course, that precautions were made special to defend from Black-White Kings, in case of their sudden appearance). It can't injure itself, but it kills all spirited, occupying the same or neighboring cell with this piece, including other Guardians. The cell is declared neighboring in the Chess World if it shares a common edge with the corresponding cell. It's well-known that retired Black King used these pieces to defend himself and his kingdom (a kingdom in the Chess World is a rectangle with M rows and N columns with some cells removed). For full protection, he had put Guardians in some cells of his kingdom, so that all cells were defended by at least one Guardian, and the number of Guardians used was minimal possible.

But, as a time had shown, it wasn't enough to protect Black King from an awful avenger. White King is now in horror. He realizes, that Black-White King had avoided punishment (it's not very amazing, because nobody had seen his corpse), and now, after killing Black King, he will want to kill White King too. So, really, this strange subject could be even another Black-White King, while nothing knows how they appear in the world (maybe except Black and White Kings. They can naturally know it, because they spent very much time together and shared the same secrets).

That's why White King urgently needs a new way of defending his kingdom, but while it's not developed yet, he wants to defend his kingdom maximally using Guardians. For this purpose he wants to put as many Guardians as possible. Of course, he understands that if he puts Guardians in every cell of his kingdom, they will kill each other immediately and the kingdom will become absolutely unsafe. As he feels a real danger, he is ready to do everything for the sake of kingdom's safety. You have a real chance to help White King to put maximal possible number of Guardians inside the kingdom, so that no one of them will kill another Guardian, and they will defend all the cells of the kingdom from invisible Black-White Kings and other genetic mutants.

Input file

On the first line of input file there are two numbers M and N, (1 ≤ N,M ≤ 200). Then M lines of N numbers follow. I-th number in J-th line is 0 if respective cell in kingdom is removed or 1 in other case.

Output file

On the first line of output file must be only one integer – maximal possible number of Guardians. Next M lines, N symbols each, represent the placement of K guardians in the kingdom. Symbol must be ".", if respective cell is empty, "G", if Guardian placed in it, or "#" if cell is removed from board. Note that you do not need to defend removed cells. If there are several solutions, output any one of them.

Example:

king.in	king.out
3 5 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1	5 G.G## .###G G.#G.

Источник: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Обсудить       Отправить решение



Версия для печати