O. [L3-3] 网格填色

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge

题目描述

九条可怜有一个 列的网格,行从上到下编号为 ,列从左到右编号为 。网格中的某些单元格已经被着色,你需要为剩下的单元格进行着色(已经着色的单元格不能重新着色),使得相同颜色的四连通块数量最小化。请构造一个满足要求的着色方案。

四连通块的定义:如果两个同色单元格共享一个公共边,则认为这两个单元格是连通的。

输入格式

第一行包含一个整数

第二行包含 个整数 ,表示网格第一行每个单元格的颜色。

第三行包含 个整数 ,表示网格第二行每个单元格的颜色。

如果 ,表示该单元格尚未着色;如果 ,表示该单元格已经被着色为颜色 。保证至少有一个单元格已被着色。

输出格式

输出两行,每行包含 个正整数 ,表示一种合法的着色方案。

输出需保证:

  • 已经着色的单元格不能重新着色,即如果 ,则必须有
  • 如果存在多种合法方案,输出其中任意一种。

样例

样例输入 1
5
1 0 1 0 2
3 3 2 0 4
样例输出 1
1 1 1 2 2
3 3 2 2 4
样例输入 2
6
1 0 2 0 0 0
3 0 0 0 4 1
样例输出 2
1 1 2 1 1 1
3 1 1 1 4 1

数据范围与提示

。保证存在一组 使得