用递归方式解决滑雪问题

wzqfwzy

滑雪问题是一个算法逻辑题, 就是像滑雪一样,只能往上下左右比自己低的地方走,问有几种方式或者最长的滑道,本来想用二叉树实现, 但需要定义父节点和4个上下左右的子节点,比较麻烦就放弃了,今天聊天时突然想起来了可以递归解决,就迅速写了代码,稍微修改下也可以处理走迷宫问题

[C] 纯文本查看 复制代码

#include <stdio.h>
//定义滑雪场,各个数值代表高度,坐标代表位置
int are[5][5] = {{ 1,  2,  3,  4, 5},
				 {16, 17, 18, 19, 6},
				 {15, 24, 25, 20, 7},
				 {14, 23, 22, 21, 8},
				 {13, 12, 11, 10, 9}};

void int_add(int *a, int n , int d)
{
	int i = 0;
	for (i = 0; i< n ; i++)
	{
		if (a[i] == 0)
		{
			a[i] = d;
			break;
		}	
	}
}

void int_pri(int *a, int n)
{
	int i = 0;
	while (a[i] != 0)
	{
		printf("%d ", a[i]);
		i++;
	}
	printf("\n");
}

void digui(int a, int b, int *his)
{
	int top = 99, bot = 99, left = 99, right = 99, i = 0;
	int len = sizeof(are[0])/sizeof(int);
	int high = sizeof(are)/sizeof(are[0]);

	int lj[32] = {0};
	//加入到滑雪路径中
	for (i = 0; i < 32; i++)
	{
		int_add(lj, 32, his[i]);
	}
	int_add(lj, 32, are[a][b]);
	//判断上下左右
	if (a > 0 )
	{
		top = are[a-1][b];
		if (top < are[a][b])
		{
			//开始递归
			digui(a-1, b, lj);
		}
	}
	if (a < high - 1)
	{
		bot = are[a+1][b];
		if (bot < are[a][b])
		{
			//开始递归
			digui(a+1, b, lj);
		}
	}
	if (b > 0 )
	{
		left = are[a][b-1];
		if (left < are[a][b])
		{
			//开始递归
			digui(a, b-1, lj);
		}
	}
	if (b < len-1 )
	{
		right = are[a][b+1];
		if (right < are[a][b])
		{
			//开始递归
			digui(a, b+1, lj);
		}
	}
	//如果此处是最低,就打印此滑道
	if (top > are[a][b] && bot > are[a][b] && left >are[a][b] && right >are[a][b] )
	{
		int_pri(lj, 32);
	}
}

int main()
{
	int lj[32] = {0};
	//输入滑雪起始位置,lj是记录滑雪路径	
	digui(2, 2, lj);
	return 0;
}

ljlVink

亲~  这边建议上洛谷多多练习呢~