D - ABC Puzzle Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

整数 N と A, B, C からなる長さ N の文字列 R,C が与えられるので、以下の問題を解いてください。

N \times N のマス目があり、最初全てのマスは空きマスです。
各マスに A, B, C のうち高々 1 文字を書き込みます。( 空きマスのままにすることも許されます )

以下の条件を全て満たすことが可能であるか判定し、可能であれば書き込み方を 1 つ出力して下さい。

  • 各行 / 各列 に A, B, C がちょうど 1 個ずつ含まれる
  • i 行目に書かれた文字の中で最も左にある文字は R の i 文字目と一致する
  • i 列目に書かれた文字の中で最も上にある文字は C の i 文字目と一致する

制約

  • N は 3 以上 5 以下の整数
  • R,C は A, B, C からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
R
C

出力

問題文中の条件を満たす書き込み方が存在しない場合、 No と 1 行に出力してください。
そうでない場合、以下の形式に従い書き込み方を出力してください。

Yes
A_1
A_2
\vdots
A_N

まず、 1 行目に Yes と出力してください。 続く N 行のうちの i 行目に、長さ N の文字列である A_i を出力してください。

  • A_i の j 文字目が . であるとき、上から i 行目、左から j 列目のマスは空きマスであることを示します。
  • A_i の j 文字目が A であるとき、上から i 行目、左から j 列目のマスに A が書き込まれたことを示します。
  • A_i の j 文字目が B であるとき、上から i 行目、左から j 列目のマスに B が書き込まれたことを示します。
  • A_i の j 文字目が C であるとき、上から i 行目、左から j 列目のマスに C が書き込まれたことを示します。

正しい書き込み方が複数存在する場合、どれを出力しても構いません。

入力例 1

5
ABCBC
ACAAB

出力例 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

出力例のマス目は以下の条件を全て満たすため、正解として扱われます。

  • 全ての行に A, B, C がちょうど 1 個ずつ含まれる
  • 全ての列に A, B, C がちょうど 1 個ずつ含まれる
  • 各行に書かれた最も左の文字は上から順に A, B, C, B, C である
  • 各列に書かれた最も上の文字は左から順に A, C, A, A, B である

入力例 2

3
AAA
BBB

出力例 2

No

この入力では、条件を満たす書き込み方は存在しません。

Score : 450 points

Problem Statement

You are given an integer N and strings R and C of length N consisting of A, B, and C. Solve the following problem.

There is a N \times N grid. All cells are initially empty.
You can write at most one character from A, B, and C in each cell. (You can also leave the cell empty.)

Determine if it is possible to satisfy all of the following conditions, and if it is possible, print one way to do so.

  • Each row and each column contain exactly one A, one B, and one C.
  • The leftmost character written in the i-th row matches the i-th character of R.
  • The topmost character written in the i-th column matches the i-th character of C.

Constraints

  • N is an integer between 3 and 5, inclusive.
  • R and C are strings of length N consisting of A, B, and C.

Input

The input is given from Standard Input in the following format:

N
R
C

Output

If there is no way to fill the grid to satisfy the conditions in the problem statement, print No in one line.
Otherwise, print one such way to fill the grid in the following format:

Yes
A_1
A_2
\vdots
A_N

The first line should contain Yes. The i-th of the subsequent N lines should contain a string A_i of length N.

  • If the j-th character of A_i is ., it indicates that the cell in the i-th row from the top and the j-th column from the left is empty.
  • If the j-th character of A_i is A, it indicates that A is written in the cell in the i-th row from the top and the j-th column from the left.
  • If the j-th character of A_i is B, it indicates that B is written in the cell in the i-th row from the top and the j-th column from the left.
  • If the j-th character of A_i is C, it indicates that C is written in the cell in the i-th row from the top and the j-th column from the left.

If there are multiple correct ways to fill the grid, you may print any of them.

Sample Input 1

5
ABCBC
ACAAB

Sample Output 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

The grid in the output example satisfies all the following conditions, so it will be treated as correct.

  • Each row contains exactly one A, one B, and one C.
  • Each column contains exactly one A, one B, and one C.
  • The leftmost characters written in the rows are A, B, C, B, C from top to bottom.
  • The topmost characters written in the columns are A, C, A, A, B from left to right.

Sample Input 2

3
AAA
BBB

Sample Output 2

No

For this input, there is no way to fill the grid to satisfy the conditions.