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

一.题目展示

二、代码解法

三、问题背景和目标

四、代码详细解释

一、题目展示

二、代码解法

#include <stdio.h>
#include <stdlib.h>

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

void dfs(int ab[][20],int a[][20],int b[],int c[],int x,int y,int n)
{
  //判断是否越界
  if(x<0 || x>=n || y<0 || y>=n)
  {
    return ;
  }
  //判断是否已经走过
  if(ab[x][y]!=-1)
  {
    return ;
  }
  //判断是否满足向北和西方射箭
  if(b[x]>0 && c[y]>0)
  {
    ab[x][y]=j;
    b[x]--;
    c[y]--;
    d[j]=a[x][y];
    j++;
  
  //判断是否到终点了
  if(x==n-1&&y==n-1)
  {
    for(int i=0;i<n;i++)
    {
      if(b[i]==0 && c[i]==0)
      {
        num++;
      }
    }
  
    if(num==n)
    {
      for(int i=0;i<j;i++)
      {
        printf("%d ",d[i]);
      }
      return ;
    }
      num=0;
}
for(int i=0;i<4;i++)
{
  dfs(ab,a,b,c,x+zhuanyix[i],y+zhuanyiy[i],n);
}
  ab[x][y]=-1;
  b[x]++;
  c[y]++;
  j--;
}
}



int main()
{
  int n;
  int b[20],c[20];
  scanf("%d",&n);
  int a[20][20];
  int ab[20][20];
  //棋盘初始化
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      ab[i][j]=-1;
    }
  }

  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      a[i][j]=i*n+j;
    }
  }

  for(int i=0;i<n;i++)
  {
    scanf("%d",&c[i]);
  }

  for(int i=0;i<n;i++)
  {
    scanf("%d",&b[i]);
  }
  dfs(ab,a,b,c,0,0,n);
  return 0;
}

三、问题背景和目标

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

四、代码详细解释

1.全局变量定义

int zhuanyix[4]={1,0,-1,0};
int zhuanyiy[4]={0,1,0,-1};
int d[200]={0};
int j=0;
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 函数（深度优先搜索函数

void dfs(int ab[][20], int a[][20], int b[], int c[], int x, int y, int n) {
    // 判断是否越界
    if (x < 0 || x >= n || y < 0 || y >= n) {
        return;
    }
    // 判断是否已经走过
    if (ab[x][y] != -1) {
        return;
    }
    // 判断是否满足向北和向西射箭的条件
    if (b[x] > 0 && c[y] > 0) {
        ab[x][y] = j;
        b[x]--;
        c[y]--;
        d[j] = a[x][y];
        j++;
        // 判断是否到达终点
        if (x == n - 1 && y == n - 1) {
            for (int i = 0; i < n; i++) {
                if (b[i] == 0 && c[i] == 0) {
                    num++;
                }
            }
            if (num == n) {
                for (int i = 0; i < j; i++) {
                    printf("%d ", d[i]);
                }
                return;
            }
            num = 0;
        }
        for (int i = 0; i < 4; i++) {
            dfs(ab, a, b, c, x + zhuanyix[i], y + zhuanyiy[i], n);
        }
        ab[x][y] = -1;
        b[x]++;
        c[y]++;
        j--;
    }
}

边界检查

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[i], y + zhuanyiy[i], n)：递归调用 dfs 函数，继续搜索下一个位置。

回溯操作

ab[x][y] = -1：将当前位置标记为未访问

b[x]++ 和 c[y]++：归还当前位置所在行和列的箭

j--：路径长度减 1。

3.主函数

int main() {
    int n;
    int b[20], c[20];
    scanf("%d", &n);
    int a[20][20];
    int ab[20][20];
    // 初始化棋盘
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ab[i][j] = -1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = i * n + j;
        }
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    dfs(ab, a, b, c, 0, 0, n);
    return 0;
}

读取输入

scanf("%d", &n)：读取棋盘的大小 n。

scanf("%d", &c[i]) 和 scanf("%d", &b[i])：分别读取每一列和每一行的箭的数量。

棋盘初始化

ab[i][j] = -1：将 ab 数组初始化为 -1，表示所有位置都未被访问。

a[i][j] = i * n + j：为每个格子分配一个唯一的编号。

举个例子:

假设棋盘大小 n=3 ，那么棋盘的样子可以表示为

对于 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 。

完整的棋盘格子编号如下：

这样通过 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]。棋盘如下：

| 0  1 |
| 2  3 |

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