루미 알고리즘

#1551실버The Tired Painter

PO 2022 학교 예선코딩출제 Axel Nilsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Ilad Rodavlas has worked as a painter all his life but is starting to get tired of his job. He brushes up, down, and up again. The same thing every day. But one day when he is about to paint a floor, divided into N × N squares, he has a brilliant idea. “Imagine if a robot could do all the work for me”, he exclaims. However, there are two problems with this idea. First, the robot can only move straight ahead, so it always paints an entire row or column with the same color. Second, Ilad cannot program. He knows, however, that you are a skilled programmer and wonders if you could help him.

Ilad has a picture that shows exactly how the floor should look in the end. The whole floor is initially unpainted. Write a program that tells the robot how to paint the floor. To avoid wasting paint, the robot must not paint the same row or column more than once.

Input

The first line contains an integer 1 ≤ N ≤ 9, the number of rows and columns on the floor that the robot will paint. Following this are N lines, each with N characters: a dot (.) for an unpainted square, S for a black square, and V for a white square.

The floor will always be possible to paint according to the given pattern. The pattern will contain at least one painted square.

Output

First, output a string with the rows and columns the robot should paint, in order. Rows are described with the numbers 1, 2, … from top to bottom, and columns with the letters A, B, … from left to right.

Then output a string with the colors the robot should use each time, with the characters V for white and S for black.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
140N ≤ 4
260No additional constraints.

예제

예제 1

입력
4
..S.
VVSV
..S.
..S.
출력
2C
VS

예제 2

입력
5
VVVVV
..S.S
VVVVS
VVVVV
..S.S
출력
C3E41
SVSVV

예제 3

입력
6
VVVVVV
VVVSVV
VVVSVV
V.VSV.
SSSSSS
V.VSV.
출력
32EDCA51
VVVSVVSV

출처 표기

출처: Programmeringsolympiaden 2022년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.