本文主要是介绍P1035 I need help,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
描述:
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,代表有T组测试数据.
每组测试数据的一行是两个整数N, M.其中N代表梅花桩的层数(2<=N<=10), M代表合法路径的数字和.
接下来有N行,第i行有i个数,代表这个N层梅花阵每层的数字,每个数字不会超过100.
输出:
对于每组测试数据,输出Yes或者No,代表是否存在这样的路径。
/*
使用的递归遍历二叉树,num计算和值。
*/
代码:
#include <stdio.h> #include <string.h> int N,M,flag; int f[12][12]; void chazhao(int i,int j,int num) { num=num+f[i][j]; if(i==N-1){ if(num==M) flag=1;} 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; scanf("%d %d",&N,&M); for(i=0;i<N;i++) for(j=0;j<=i;j++) scanf("%d",&f[i][j]); chazhao(0,0,0); if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }
这篇关于P1035 I need help的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!