分数: 300 点
问题陈述
有一个 N \times N 网格。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
你被给予 N \times N 字符 S_{1,1}, \dots , S_{N,N}。每个字符都是一个数字 (0 to 9)或 ?。确定是否可以替换每个 ? 用一位数字满足以下条件,如果可能,输出一种这样的替换方式。
对于每个 1 \le i,j \le N,写 S_{i,j} 作为单元格中的整数 (i,j).
对于来自单元格的路径 (1,1) 到单元格 (N,N) 通过仅重复移动到右侧或向下的相邻单元格,让 路径的 分数 游戏的 是路径上单元格中写入的整数之和(包括起点和终点)。
那么,对于所有 \binom{2N-2}{N-1} 可能的路径,分数都是相等的。
约束
- 2 \le N \le 100
- S_{i,j} 是一个数字 (
0to9)或?.
输入
输入由标准输入按以下格式给出:
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