本文共 1779 字，大约阅读时间需要 5 分钟。

Johnny Q 在你的帮助下终于进入了城堡，眼前是一条恐怖的黑水河。河中有大量传说中的食人怪兽——法克鱿，同时还有一个N层正三角梅花桩阵，每个桩上都印有一个数字。比如，图中展示的是一个4层的正三角梅花桩阵。

Johnny Q 只能从离他最近的即这个三角木桩阵的最上一个木桩开始，一个桩一个桩地跳到对岸去。每次他只能向左下或右下跳一次，跳的距离只能是一个单位步长。比如，最上面的7只能跳到3和8，而3又只能跳到4和1。这样的跳跃对身手矫健的Johnny Q 来说显然是小菜一碟，但CK也不是盏省油的灯，要想跳过还有一个要求：从你第一个桩跳到最后一个桩，所经过桩上的数字之和必须要等于M，否则就算跳到了最后一层的桩上，这个桩也会沉下去。例如，当M=21时，路径7->3->1->10是合法的，7->3->4->7也是合法的路径。现在你需要帮助Johnny Q判断是否存在这样的路径。

输入包括T组测试数据。每组测试数据包括两个整数N和M，其中N代表梅花桩的层数（2 ≤ N ≤ 10），M代表合法路径的数字和。接下来有N行，第i行有i个数字，代表这个N层梅花阵每层的数字，每个数字不会超过100。

输出对于每组测试数据，输出"Yes"或"No"，代表是否存在这样的路径。

技术实现思路

我们可以使用深度优先搜索（DFS）来遍历所有可能的路径，并检查路径和是否等于M。具体步骤如下：

代码实现

#include 
   
    #include 
    
     int N, M, flag = 0;int f[12][12]; // 假设层数最多为10层，位置索引从0开始void chazhao(int i, int j, int num) {    num += f[i][j]; // 加上当前桩的数字    if (i == N - 1) { // 到达最后一层        if (num == M) {            flag = 1;        }        return;    } else {        chazhao(i + 1, j, num); // 左下方向        chazhao(i + 1, j + 1, num); // 右下方向    }}int main() {    int T, i, j, k;    scanf("%d", &T);    while (T--) {        flag = 0;        // 读取N和M        scanf("%d %d", &N, &M);        // 读取N层的数字        for (i = 0; i < N; ++i) {            scanf("%d", &f[i][0]);            for (j = 1; j < i; ++j) {                scanf("%d", &f[i][j]);            }        }        // 开始递归检查        chazhao(0, 0, f[0][0]);        printf(flag ? "Yes" : "No");    }}
    
   

逐步解释

这种方法确保了所有可能的路径都被检查，能够正确判断是否存在满足条件的路径。

转载地址：http://ddvfk.baihongyu.com/