首页 > 代码库 > 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];>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。