#P3525. [Poi2014]Snake

    ID: 2736 传统题 10000ms 512MiB 尝试: 5 已通过: 2 难度: 10 上传者: 标签>难度分类省选/NOI-动态规划记忆化搜索枚举与搜索暴力枚举构造与建模对称性分析路径恢复CF2900ByDzy

[Poi2014]Snake

[POI2014] Snake

题目描述

在一块 3×n3\times n 的棋盘上,一条蛇恰好占满所有格子。蛇身各节依次标为 1,2,…,3n1,2,\ldots,3n,编号连续的两节所在的格子必须共用一条边。下图展示了 3×93\times9 棋盘上的一种合法蛇形。

蛇身从 1 到 27 顺序连接,填满三行九列

现在棋盘上的一些编号已经被擦掉。请补全棋盘,恢复任意一种与已知编号一致的蛇形。保证有解。

输入格式

第一行一个整数 nn。接下来三行,每行 nn 个整数。第 ii 行第 jj 列的整数 ai,ja_{i,j} 为 00 时,表示该格编号未知,否则表示该格的已知编号。

输出格式

输出三行,每行 nn 个整数,表示补全后的棋盘。所有输出数字恰好是 11 到 3n3n 的一个排列,不能改变已知编号,且任意两个连续编号所在格子必须共边。有多种解时可输出任意一种。

样例 #1

9
0 0 5 0 17 0 0 0 21
8 0 0 3 16 0 0 25 0
0 0 0 0 0 0 0 0 23
7 6 5 4 17 18 19 20 21
8 1 2 3 16 15 26 25 22
9 10 11 12 13 14 27 24 23

数据范围

1≤n≤10001\le n\le1000,0≤ai,j≤3n0\le a_{i,j}\le3n。

原赛累计分值 nn 的上限
15%15\% 1010
40%40\% 4040
70%70\% 300300
100%100\% 10001000