UVa 10285 Longest Run on a Snowboard

本題連結
題意：
　　本題給予一個區域內的每個點的高度，滑雪只能由高的點往低的點滑，要求出在這個區域內最多能滑幾個點(滑最遠的方式)。

想法：
　　用一一枚舉的方式，也就是每個點都走走看。
我們定義遞迴式int find_longest (i,j,length) 是回傳area[i][j]這個點所能走的最遠長度。把所有點都算出其最遠長度，在從所有點中選出最大值輸出。


    

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N,R,C,area[101][101];
	char name[100];
	// 定義find_longest函數為回傳該點(area[i][j])盡可能走的最遠長度
	int find_longest (int i,int j,int length) // length為目前已經走的長度
	{
	int a=0, b=0, c=0, d=0;
	if (i-1>=0 && area[i-1][j]<area[i][j]) a = find_longest (i-1,j,length+1); //往上走
	if (i+1<R && area[i+1][j]<area[i][j]) b = find_longest (i+1,j,length+1); //往下走
	if (j-1>=0 && area[i][j-1]<area[i][j]) c = find_longest (i,j-1,length+1); //往左走
	if (j+1<C && area[i][j+1]<area[i][j]) d = find_longest (i,j+1,length+1); //往右走
	if (a || b || c || d) { //表示至少還有一個方向能走，回傳最遠的長度
	a = max(a,b); a = max(a,c); a = max(a,d);
	return a;
	}
	else return length; //四個方向都不能在往下走了，表示走到死路，回傳當前長度
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	scanf("%d",&N);
	while (N--)
	{
	scanf("%s%d%d",name,&R,&C);
	for (int i=0; i<R; i++)
	for (int j=0; j<C; j++)
	scanf("%d",&area[i][j]);
	int Max=0;
	for (int i=0; i<R; i++) // 一一枚舉每個點，選出最遠的長度
	for (int j=0; j<C; j++){
	int t = find_longest(i,j,1); // 一開始長度為1(自己也算)
	if (t > Max) Max = t;
	}
	printf("%s: %d\n",name,Max);
	}
	return 0;
	}

view raw [UVa] 10285 Longest Run on a Snowboard.cpp hosted with ❤ by GitHub