/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N \times N のマス目があります。上から i 行目、左から j 列目のマスを (i,j) で表します。
N \times N 個の文字 S_{1,1}, \dots , S_{N,N} が与えられます。各文字は数字（0～9）または ? です。? をそれぞれ数字に置き換えることで以下の条件を満たせるか判定し、可能ならばそのような置き換え方を 1 つ出力して下さい。
1 \le i,j \le N についてマス (i,j) に S_{i,j} を整数として書き込む。
右または下に隣接するマスへの移動のみを繰り返してマス (1,1) からマス (N,N) まで到達する経路について、経路上に含まれるマス（始点・終点を含む）に書かれた整数の総和を経路のスコアとする。
このとき、\binom{2N-2}{N-1} 通りある経路について、スコアは全て等しい。
制約
- 2 \le N \le 100
- S_{i,j} は数字（
0～9）または?
入力
入力は以下の形式で標準入力から与えられる。
N
S_{1,1}S_{1,2}\ldotsS_{1,N}
S_{2,1}S_{2,2}\ldotsS_{2,N}
\vdots
S_{N,1}S_{N,2}\ldotsS_{N,N}
出力
条件を満たす置き換えが不可能な場合、-1 を出力せよ。可能な場合、置き換え後の S_{1,1}, \dots , S_{N,N} を以下の形式で出力せよ。
S_{1,1}S_{1,2}\ldotsS_{1,N}
S_{2,1}S_{2,2}\ldotsS_{2,N}
\vdots
S_{N,1}S_{N,2}\ldotsS_{N,N}
解が複数存在する場合は、どれを出力しても正解とみなされる。
入力例 1
3 101 0?? 1??
出力例 1
101 010 101
全ての経路のスコアが 3 になるように ? を数字に置き換えることが出来ます。
入力例 2
4 2026 ?2?8 ???? ?214
出力例 2
-1
どのような置き換え方をしても条件を満たすことが出来ません。
入力例 3
2 99 99
出力例 3
99 99
Score : 300 points
Problem Statement
There is an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.
You are given N \times N characters S_{1,1}, \dots , S_{N,N}. Each character is a digit (0 to 9) or ?. Determine if it is possible to replace each ? with a digit to satisfy the following condition, and if possible, output one such way of replacement.
For each 1 \le i,j \le N, write S_{i,j} as an integer in cell (i,j).
For a path from cell (1,1) to cell (N,N) by repeating moves only to adjacent cells to the right or down, let the score of the path be the sum of the integers written in the cells on the path (including the start and end points).
Then, for all \binom{2N-2}{N-1} possible paths, the scores are all equal.
Constraints
- 2 \le N \le 100
- S_{i,j} is a digit (
0to9) or?.
Input
The input is given from Standard Input in the following format:
N
S_{1,1}S_{1,2}\ldotsS_{1,N}
S_{2,1}S_{2,2}\ldotsS_{2,N}
\vdots
S_{N,1}S_{N,2}\ldotsS_{N,N}
Output
If it is impossible to make a replacement that satisfies the condition, output -1. If possible, output S_{1,1}, \dots , S_{N,N} after the replacement in the following format:
S_{1,1}S_{1,2}\ldotsS_{1,N}
S_{2,1}S_{2,2}\ldotsS_{2,N}
\vdots
S_{N,1}S_{N,2}\ldotsS_{N,N}
If there are multiple solutions, any of them will be accepted.
Sample Input 1
3 101 0?? 1??
Sample Output 1
101 010 101
It is possible to replace ? with digits so that the scores of all paths are 3.
Sample Input 2
4 2026 ?2?8 ???? ?214
Sample Output 2
-1
No replacement can satisfy the condition.
Sample Input 3
2 99 99
Sample Output 3
99 99