题目 1834- 路径之谜

科技前沿 • 2025-04-10 19:50 • 阅读 24

大家好，我是讯享网，很高兴认识大家。

题目

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

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

假设城堡地面是 n x n 个方格。【如图1.png】所示。
在这里插入图片描述
讯享网

按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）

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

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

有时是可以的，比如图1.png中的例子。

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

输入
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）

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

解题思路

本题第一反应是采用深度优先搜索，且本题数据量不大，可以使用典型的递归加上回溯来进行搜索。递归函数每一次确定下一步走到哪，但是需要注意“下标是否越界以及下一步想要走到的点是否曾经到达过（每一个点只能经过一次）”；如果恰好走到终点，则判断射箭总数是否符合要求，若符合，之后的递归便不需要再进行，此处通过F的值来确定是否找到符合要求的情况。

易错点

由于本题采用了回溯的方法，因此，在找到符合要求的情况后，需要立即输出具体路线（或者用非回溯数组存储起来，在main中输出），若在DFS结束后输出，因为回溯，数组会重回初态，路线也随之消失。

代码

#include<stdio.h> int N,F=0;//F标定是否找到 int dir[2][4] = { 
   { 
   -1,+1,0,0},{ 
   0,0,-1,+1}};//上下左右 int paths[450];//记录路线的数组 int lenp=0; int hash_n[21],hash_w[21]; int points[21][21];//记录同一个网格是否走了两次 void DFS(int north[N], int west[N], int now_x, int now_y){ 
    int i,j,tx,ty; if (now_y==N-1 && now_x==N-1)//达到终点 { 
    for (i=0;i<N;i++) if (north[i]!=hash_n[i] || west[i]!=hash_w[i]) break; if (i==N) { 
    F = 1; for (j=0;j<lenp;j++) { 
    if (j!=0) printf(" "); printf("%d",paths[j]); } } } else { 
    for (i=0;i<4;i++) { 
    tx = now_x+dir[0][i]; ty = now_y+dir[1][i]; if (F==0 && tx>=0 && ty>=0 && tx<N && ty<N && points[tx][ty]==0) { 
    hash_w[tx]++; hash_n[ty]++; points[tx][ty] = 1; paths[lenp++] = tx*N+ty; DFS(north,west,tx,ty); points[tx][ty] = 0;//回溯 lenp--; hash_w[tx]--; hash_n[ty]--; } } } } int main() { 
    int i; scanf("%d",&N); int north[N];//北边的箭靶上的数字（自西向东） int west[N];//西边的箭靶上的数字（自北向南） for (i=0;i<N;i++)//读入靶子上的箭数目 scanf("%d",&north[i]); for (i=0;i<N;i++) scanf("%d",&west[i]); hash_w[0]++;hash_n[0]++;//起点 points[0][0] = 1; paths[lenp++] = 0;//走过的第一个点是起点 DFS(north,west,0,0); return 0; }

题目 1834- 路径之谜

题目

解题思路

易错点

代码

相关推荐