【蓝桥杯刷题实战】路径之谜

一.标题展示

二、代码解法

三、题目背景和目的

四、代码详细解释


一、标题展示

二、代码解法

1. #include <stdio.h>
2. #include <stdlib.h>
4. int zhuanyix[4]={1,0,-1,0};
5. int zhuanyiy[4]={0,1,0,-1};
6. int d[200]={0};
7. int j=0;
8. int num=1;
10. void dfs(int ab[][20],int a[][20],int b[],int c[],int x,int y,int n)
11. {
12.   //判断是否越界
13.   if(x<0 || x>=n || y<0 || y>=n)
14.   {
15.     return ;
16.   }
17.   //判断是否已经走过
18.   if(ab[x][y]!=-1)
19.   {
20.     return ;
21.   }
22.   //判断是否满足向北和西方射箭
23.   if(b[x]>0 && c[y]>0)
24.   {
25.     ab[x][y]=j;
26.     b[x]--;
27.     c[y]--;
28.     d[j]=a[x][y];
29.     j++;
30.   
31.   //判断是否到终点了
32.   if(x==n-1&&y==n-1)
33.   {
34.     for(int i=0;i<n;i++)
35.     {
36.       if(b[i]==0 && c[i]==0)
37.       {
38.         num++;
39.       }
40.     }
41.   
42.     if(num==n)
43.     {
44.       for(int i=0;i<j;i++)
45.       {
46.         printf("%d ",d[i]);
47.       }
48.       return ;
49.     }
50.       num=0;
51. }
52. for(int i=0;i<4;i++)
53. {
54.   dfs(ab,a,b,c,x+zhuanyix[i],y+zhuanyiy[i],n);
55. }
56.   ab[x][y]=-1;
57.   b[x]++;
58.   c[y]++;
59.   j--;
60. }
61. }
65. int main()
66. {
67.   int n;
68.   int b[20],c[20];
69.   scanf("%d",&n);
70.   int a[20][20];
71.   int ab[20][20];
72.   //棋盘初始化
73.   for(int i=0;i<n;i++)
74.   {
75.     for(int j=0;j<n;j++)
76.     {
77.       ab[i][j]=-1;
78.     }
79.   }
81.   for(int i=0;i<n;i++)
82.   {
83.     for(int j=0;j<n;j++)
84.     {
85.       a[i][j]=i*n+j;
86.     }
87.   }
89.   for(int i=0;i<n;i++)
90.   {
91.     scanf("%d",&c[i]);
92.   }
94.   for(int i=0;i<n;i++)
95.   {
96.     scanf("%d",&b[i]);
97.   }
98.   dfs(ab,a,b,c,0,0,n);
99.   return 0;
100. }

复制代码

三、题目背景和目的

这个标题观察的是DFS(深度优先搜刮)算法，代码用了回溯的解法，先看代码，我们要想象有一个n*n的棋盘，每一行和每一列都要有一定数量的箭，我们要从棋盘左上角(0，0)出发，走到右下角(n-1，n-1)。在走过每一个格子时，要分别向这一行和这一列各射一箭(前提是这每一行每一列还有箭，当走到终点时，每一行每一列的箭刚好用完，就说明走的是一个有效的路径，末了代码就会输出这个路径。
四、代码详细解释

1.全局变量定义

1. int zhuanyix[4]={1,0,-1,0};
2. int zhuanyiy[4]={0,1,0,-1};
3. int d[200]={0};
4. int j=0;
5. int num=1;

复制代码

zhuanyix和zhuanyiy:这两个数组表示四个方向的偏移量zhuanyix[0]=1和zhuanyiy[0]=0表示向右移动zhuanyix[1] = 0 和 zhuanyiy[1] = 1 表示向下移动；zhuanyix[2] = -1 和 zhuanyiy[2] = 0 表示向左移动；zhuanyix[3] = 0 和 zhuanyiy[3] = -1 表示向上移动。
d数组:用于存储路径，每个元素存储路径上颠末的格子的编号。
j:d数组的索引，记载当前路径的长度。
num：用于统计到达终点时，箭用完的行和列的数量。
2. dfs 函数（深度优先搜刮函数

1. void dfs(int ab[][20], int a[][20], int b[], int c[], int x, int y, int n) {
2.     // 判断是否越界
3.     if (x < 0 || x >= n || y < 0 || y >= n) {
4.         return;
5.     }
6.     // 判断是否已经走过
7.     if (ab[x][y] != -1) {
8.         return;
9.     }
10.     // 判断是否满足向北和向西射箭的条件
11.     if (b[x] > 0 && c[y] > 0) {
12.         ab[x][y] = j;
13.         b[x]--;
14.         c[y]--;
15.         d[j] = a[x][y];
16.         j++;
17.         // 判断是否到达终点
18.         if (x == n - 1 && y == n - 1) {
19.             for (int i = 0; i < n; i++) {
20.                 if (b[i] == 0 && c[i] == 0) {
21.                     num++;
22.                 }
23.             }
24.             if (num == n) {
25.                 for (int i = 0; i < j; i++) {
26.                     printf("%d ", d[i]);
27.                 }
28.                 return;
29.             }
30.             num = 0;
31.         }
32.         for (int i = 0; i < 4; i++) {
33.             dfs(ab, a, b, c, x + zhuanyix[i], y + zhuanyiy[i], n);
34.         }
35.         ab[x][y] = -1;
36.         b[x]++;
37.         c[y]++;
38.         j--;
39.     }
40. }

复制代码

界限检查

if (x < 0 || x >= n || y < 0 || y >= n)：如果当前位置 (x, y) 超出了棋盘的界限，函数直接返回，停止继承搜刮。
if (ab[x][y] != -1)：如果当前位置已经被访问过（ab[x][y] 不即是 -1），函数直接返回，克制重复访问。
射箭条件检查

if (b[x] > 0 && c[y] > 0)：如果当前位置所在行和列都还有箭，那么可以继承进步。
ab[x][y] = j：标记当前位置已经被访问，并记载访问次序。
b[x]-- 和 c[y]--：消耗当前位置所在行和列的各一支箭。
d[j] = a[x][y]：将当前格子的编号存入路径数组 d 中。
j++：路径长度加 1。
终点检查

if (x == n - 1 && y == n - 1)：如果到达了右下角的终点，检查所有行和列的箭是否都被用完。
for (int i = 0; i < n; i++)：遍历每一行和每一列，统计箭用完的数量。
if (num == n)：如果所有行和列的箭都被用完，输出路径
num = 0：重置 num 变量，为下一次搜刮做准备
递归搜刮

for (int i = 0; i < 4; i++)：从当前位置向四个方向进行递归搜刮。
dfs(ab, a, b, c, x + zhuanyix, y + zhuanyiy, n)：递归调用 dfs 函数，继承搜刮下一个位置。
回溯操作

ab[x][y] = -1：将当前位置标记为未访问
b[x]++ 和 c[y]++：归还当前位置所在行和列的箭
j--：路径长度减 1。
3.主函数

1. int main() {
2.     int n;
3.     int b[20], c[20];
4.     scanf("%d", &n);
5.     int a[20][20];
6.     int ab[20][20];
7.     // 初始化棋盘
8.     for (int i = 0; i < n; i++) {
9.         for (int j = 0; j < n; j++) {
10.             ab[i][j] = -1;
11.         }
12.     }
13.     for (int i = 0; i < n; i++) {
14.         for (int j = 0; j < n; j++) {
15.             a[i][j] = i * n + j;
16.         }
17.     }
18.     for (int i = 0; i < n; i++) {
19.         scanf("%d", &c[i]);
20.     }
21.     for (int i = 0; i < n; i++) {
22.         scanf("%d", &b[i]);
23.     }
24.     dfs(ab, a, b, c, 0, 0, n);
25.     return 0;
26. }

复制代码

读取输入

scanf("%d", &n)：读取棋盘的巨细 n。
scanf("%d", &c) 和 scanf("%d", &b)：分别读取每一列和每一行的箭的数量。
棋盘初始化

ab[j] = -1：将 ab 数组初始化为 -1，表示所有位置都未被访问。
a[j] = i * n + j：为每个格子分配一个唯一的编号。
举个例子:
假设棋盘巨细 n=3 ，那么棋盘的样子可以表示为
列 0列 1列 2行 0a[0][0]a[0][1]a[0][2]行 1a[1][0]a[1][1]a[1][2]行 2a[2][0]a[2][1]a[2][2] 对于 a[0][0] ：此时 i = 0 ，j = 0 ，代入 i * n + j 可得 0 * 3 + 0 = 0 ，以是 a[0][0] 的编号是 0 。
对于 a[0][1] ：i = 0 ，j = 1 ，盘算 0 * 3 + 1 = 1 ，其编号是 1 。
对于 a[1][0] ：i = 1 ，j = 0 ，1 * 3 + 0 = 3 ，编号为 3 。
对于 a[2][2] ：i = 2 ，j = 2 ，2 * 3 + 2 = 8 ，编号是 8 。
完整的棋盘格子编号如下：
列 0列 1列 2行 0012行 1345行 2678
如许通过 i * n + j 就为棋盘上的每个格子都赋予了一个独特的编号，方便在后续代码中对格子进行标识和处理，比如在记载路径时（d[j] = a[x][y]; 这行代码中，就是将格子编号记载到路径数组 d 中 ） 。

调用 dfs 函数：

dfs(ab, a, b, c, 0, 0, n)：从左上角 (0, 0) 开始进行深度优先搜刮。
简单例子

假设 n = 2，每一列的箭数 c 为 [1, 1]，每一行的箭数 b 为 [1, 1]。棋盘如下：

1. | 0  1 |
2. | 2  3 |

复制代码

• 从 (0, 0) 位置开始，b[0] = 1，c[0] = 1，满意射箭条件，消耗箭，标记位置，记载路径。
  
• 向右移动到 (0, 1)，b[0] = 0，c[1] = 1，满意射箭条件，消耗箭，标记位置，记载路径。
  
• 向下移动到 (1, 1)，到达终点，检查发现所有行和列的箭都被用完，输出路径 0 1 3。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。