Problem Statement
小明冒充 $X$ 星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 $n\times n$ 个方格。如图所示。
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 $n$ 个靶子）
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如如图中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
第一行一个整数 $N(0<N<20)$，表示地面有 $N \times N$ 个方格。
第二行 $N$ 个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行 $N$ 个整数，空格分开，表示西边的箭靶上的数字（自北向南）
Output
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号 $:0,1,2,3 \cdots $。
比如，图中的方块编号为：
1
2
3
4
|
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
|
Sample Output
1
|
0 4 5 1 2 3 7 11 10 9 13 14 15
|
Constraints
时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛
Solving
利用深度优先搜索遍历左上角到右下角的所有路径， 初始化一个pre数组用于记录每个节点的前驱节点，每次到一个新的点位，减去相应点对应的两个靶子上的一个箭数，到达终点时，检查所有靶子上是否还存有箭矢，若都没有，则证明此条路径是答案路径，此时输出当前路径的所有前驱节点，退出程序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
const int N = 21;
const int M = 0;
int nor[N];
int wes[N];
int pre[N*N];//用于记录第i个点的前驱节点
bool vis[N][N];
int n;
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
bool check(int x,int y)
{
return x>0&&x<=n&&y>0&&y<=n;
}
//检查这条路径是不是答案路径
bool checklegal()
{
for(int i=1;i<=n;i++)
if(wes[i]||nor[i]) return false;
return true;
}
//用于计算当前点的映射坐标
int compute(int x,int y)
{
return x*n-(n-y)-1;
}
//用于打印前驱节点的dfs函数
void print(int x)
{
if(pre[x]==-1) return;//直到回溯到起点截止
print(pre[x]);
//所有回溯完成后输出,保证正序输出
cout << x << ' ';
}
void dfs(int x,int y)
{
if(x==n&&y==n)
{
if(checklegal())
{
cout << 0 << ' ';
print(n*n-1);//从终点开始打印
exit(0);
}
else
return;
}
for(int i=0;i<4;i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(check(nx,ny)&&!vis[nx][ny]&&wes[nx]>=1&&nor[ny]>=1)//如果下一个节点对应的靶子上都至少有一个箭
{
vis[nx][ny] = true;
--wes[nx];
--nor[ny];
//记录下一个点(nx,ny)的前驱节点是(x,y)
pre[compute(nx,ny)] = compute(x,y);
dfs(nx,ny);
//回溯
++wes[nx];
++nor[ny];
vis[nx][ny] = false;
}
}
}
void solve()
{
cin >> n;
//注意北边和西边的靶子分别与横纵坐标的对应关系
for(int i=1;i<=n;i++)cin >> nor[i];
for(int i=1;i<=n;i++)cin >> wes[i];
//初始化起点
nor[1]--;
wes[1]--;
pre[0] = -1;
vis[1][1] = true;
dfs(1,1);
return;
}
|