Angle Beats
시간 제한2초메모리 제한512 MB
격자 위에 겹치지 않는 L자형과 I자형 트로미노를 최대한 많이 놓는다. 두 모양 모두 중심은 '+'여야 하고, L자형은 '*'도 중심이 될 수 있으며 나머지 칸은 '.'이어야 한다.
문제
You have a rectangular board consisting of n × m squares. Each square contains a character which is either “*”, “+”, or “.”.
A tromino is a figure formed by a square of the board, called the center, and two other squares, each sharing an edge with the center. A tromino is L-shaped if these two squares have a common vertex, and I-shaped otherwise.
You can draw some disjoint trominoes on the board. The center of an I-shaped tromino must contain “+”. The center of an L-shaped tromino must contain either “*” or “+”. All non-center squares of all trominoes must contain “.”.
Your goal is to draw the maximum number of non-intersecting polyominoes.
입력
The first line contains two integers n and m: the number of rows and columns of the board (2 ≤ n, m ≤ 100).
Each of the next n lines contains m characters, and each character is either “*”, “+”, or “.”. Together, these lines describe the board.
출력
Print n lines, each containing m characters: the board with trominoes on it. If a square belongs to some tromino, output a lowercase English letter, and if not, output the character contained in this square. Squares of the same tromino must contain the same letter. Squares which share an edge and belong to different trominoes must contain different letters.
If there are several possible answers, print any one of them.