欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深搜

程序员文章站 2022-07-12 21:50:48
...



7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(图1)

图1给出了一个数字三角形。
从指定的一个数往下走,可以走到下一层上和它最近的左边的那个数或者右边的那个数。
任务:
给定数字三角形中的一个位置,求从它开始所能到达的最大数 输入 输入数据包含多组测试数据,

对于每组测试数据:
输入的第一行是一个整数N (0 <= N <= 100),给出三角形的行数。
(当N为0时,表示测试结束,你不需要处理本组数据)
下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
接下来一行有两个数,R和C,表示起始点位于第R行第C个位置。
输出 输出若干行,每行对应一组测试数据的结果。 样例输入
1
2
1 1
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
1 1
6
88 
97 26 
39 16 47 
94 25 66 4 
64 49 20 36 27 
37 87 29 37 10 40 
2 1
0
样例输出
2
8
97


这道题是上次选拔赛的题,应该是老师新出的题,所以百度上一直没有找到题解,刚刚问了一下过了的同学才知道,自己的解题思路完全有问题,问题所在居然是题理解错了,想得太简单,然而这道题要用到深搜的思想来做。。

下面是代码:

#include<cstdio>
using namespace std;
const int MAXN=100;
int a[MAXN][MAXN];
bool used[MAXN][MAXN];
int dir[2][2]={1,0,1,1};
int ans;
int n;
void dfs(int x,int y)
{
	used[x][y]=true;
	for(int i=0;i<2;i++)
	{
		int nx=x+dir[i][0];
		int ny=y+dir[i][1];
		if(nx>=0 && nx<n && ny>=0 && ny<n && nx>=ny)
		{
			if(a[nx][ny]>ans)
			{
				ans=a[nx][ny];
			}
			if(!used[nx][ny])
				dfs(nx,ny);
		} 
	}
}
int main()
{
	while(~scanf("%d",&n)&&n)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<=i;j++)
			{
				scanf("%d",&a[i][j]);
				used[i][j]=false;
			}
		}
		int x,y;
		scanf("%d%d",&x,&y);
		ans=a[x-1][y-1];
		dfs(x-1,y-1);
		printf("%d\n",ans);
	}
	return 0;
}



7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(图1)

图1给出了一个数字三角形。
从指定的一个数往下走,可以走到下一层上和它最近的左边的那个数或者右边的那个数。
任务:
给定数字三角形中的一个位置,求从它开始所能到达的最大数。 输入 输入数据包含多组测试数据,

对于每组测试数据:
输入的第一行是一个整数N (0 <= N <= 100),给出三角形的行数。
(当N为0时,表示测试结束,你不需要处理本组数据)
下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
接下来一行有两个数,R和C,表示起始点位于第R行第C个位置。
输出 输出若干行,每行对应一组测试数据的结果。 样例输入
1
2
1 1
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
1 1
6
88 
97 26 
39 16 47 
94 25 66 4 
64 49 20 36 27 
37 87 29 37 10 40 
2 1
0
样例输出
2
8
97