#P8642. [蓝桥杯 2016 国 AC] 路径之谜(疑似错题)

[蓝桥杯 2016 国 AC] 路径之谜(疑似错题)

题目背景

本题疑似为错题,目前还没有能通过 https://www.luogu.com.cn/ticket/AGHR483394 中 Hack 数据的解法。为了保证本题尽可能可做,我们已经根据蓝桥杯中本题实际的测试数据范围进行缩小,原数据范围 N20N\leq 20 应该完全无解。

题目描述

小明冒充 XX 星球的骑士,进入了一个奇怪的城堡。

城堡里边什么都没有,只有方形石头铺成的地面。

假设城堡地面是 n×nn\times n 个方格。如图所示。

按习俗,骑士要从西北角走到东南角。

可以横向或纵向移动,但不能斜着走,也不能跳跃。

每走到一个新方格,就要向正北方和正西方各射一箭。

(城堡的西墙和北墙内各有 nn 个靶子)

同一个方格只允许经过一次。但不必做完所有的方格。

如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?

有时是可以的,比如如图中的例子。

本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)

输入格式

第一行一个整数 N(1N10)N(1\leq N\leq 10),表示地面有 N×NN \times N 个方格。

第二行 NN 个整数,空格分开,表示北边的箭靶上的数字(自西向东)

第三行 NN 个整数,空格分开,表示西边的箭靶上的数字(自北向南)

输出格式

一行若干个整数,表示骑士路径。

为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号 :0,1,2,3:0,1,2,3 \cdots

比如,图中的方块编号为:

0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15
4
2 4 3 4
4 3 3 3
0 4 5 1 2 3 7 11 10 9 13 14 15

提示

时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛