首页 > 代码库 > UVa 10285 - Longest Run on a Snowboard

UVa 10285 - Longest Run on a Snowboard

题目:给你一个二维的矩阵,找到一个点,每次可以移动到上下左右相邻的位置,求最长的单调路径。

分析:贪心,dp,搜索。这道题数据较小,怎么做都可以。

            这里使用贪心算法:

            首先,将所有点按照权值排序(每个点一定被值更大的点更新);

            然后,按顺序更新排序后,每个点更新周围的点;

            最后,找到最大值输出即可。

说明:╮(╯▽╰)╭竟然拍了1000+,还以为这种方法比较快呢(数据分布啊╮(╯▽╰)╭)。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

typedef struct nodep
{
	int value,x,y;
}point;
point now,Node[10004];

char buf[256];
int  maps[102][102];
int  imap[102][102];
int  dmap[102][102];

int cmp1( point a, point b )
{
	return a.value > b.value;
}

int cmp2( point a, point b )
{
	return a.value < b.value;
}

int main()
{
	int T,R,C,dxy[4][2] = {1,0,0,1,-1,0,0,-1};
	while ( ~scanf("%d",&T) )
	while ( T -- ) {
		scanf("%s%d%d",buf,&R,&C);
		int count = 0;
		for ( int i = 1 ; i <= R ; ++ i )
		for ( int j = 1 ; j <= C ; ++ j ) {
			scanf("%d",&maps[i][j]);
			imap[i][j] = dmap[i][j] = 1;
			Node[count].value = http://www.mamicode.com/maps[i][j];>