九条可怜有一个 行 列的网格,行从上到下编号为 到 ,列从左到右编号为 到 。网格中的某些单元格已经被着色,你需要为剩下的单元格进行着色(已经着色的单元格不能重新着色),使得相同颜色的四连通块数量最小化。请构造一个满足要求的着色方案。
四连通块的定义:如果两个同色单元格共享一个公共边,则认为这两个单元格是连通的。
第一行包含一个整数 。
第二行包含 个整数 ,表示网格第一行每个单元格的颜色。
第三行包含 个整数 ,表示网格第二行每个单元格的颜色。
如果 ,表示该单元格尚未着色;如果 ,表示该单元格已经被着色为颜色 。保证至少有一个单元格已被着色。
输出两行,每行包含 个正整数 ,表示一种合法的着色方案。
输出需保证:
5 1 0 1 0 2 3 3 2 0 4
1 1 1 2 2 3 3 2 2 4
6 1 0 2 0 0 0 3 0 0 0 4 1
1 1 2 1 1 1 3 1 1 1 4 1
。保证存在一组 使得 。