← 返回题目列表

AtCoder · arc214_a

A. 相同的总和网格路径

中文机器翻译题面 查看原题

分数: 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} 是一个数字 (0 to 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