|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||117||82||74||71.845%|
You are catering a party for some children, and you are serving them a cake in the shape of a grid with R rows and C columns. Your assistant has started to decorate the cake by writing every child's initial in icing on exactly one cell of the cake. Each cell contains at most one initial, and since no two children share the same initial, no initial appears more than once on the cake.
Each child wants a single rectangular (grid-aligned) piece of cake that has their initial and no other child's initial(s). Can you find a way to assign every blank cell of the cake to one child, such that this goal is accomplished? It is guaranteed that this is always possible. There is no need to split the cake evenly among the children, and one or more of them may even get a 1-by-1 piece; this will be a valuable life lesson about unfairness.
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with two integers R and C. Then, there are R more lines of Ccharacters each, representing the cake. Each character is either an uppercase English letter (which means that your assistant has already added that letter to that cell) or
?(which means that that cell is blank).
For each test case, output one line containing
Case #x: and nothing else. Then output Rmore lines of C characters each. Your output grid must be identical to the input grid, but with every
? replaced with an uppercase English letter, representing that that cell appears in the slice for the child who has that initial. You may not add letters that did not originally appear in the input. In your grid, for each letter, the region formed by all the cells containing that letter must be a single grid-aligned rectangle.
If there are multiple possible answers, you may output any of them.
3 3 3 G?? ?C? ??J 3 4 CODE ???? ?JAM 2 2 CA KE
Case #1: GGJ CCJ CCJ Case #2: CODE COAE JJAM Case #3: CA KE
The sample output displays one set of answers to the sample cases. Other answers may be possible.