测试数据来自 nnu_contest/1298

E. Maze

时间限制:1s

空间限制:64MB

本题分值:200

题目描述

现有 \(n\) 行 \(m\) 列的网格，每个格子上写有一个数字 \(a_{ij}\) 。

若两个 相邻 的格子 \(x,y\) 上的数字满足：格子 \(x\) 上面的数字 小于 \(y\) 上面的数字，则 \(x\) 可以走一步到达 \(y\) 。

• 相邻指的是两个格子位于同一行，且列号相差 \(1\) ，或处于同一列，且行号相差 \(1\) 。特别地，若相邻的格子数字 相同，则它们 互相不可达 。

从左上角点 \((1,1)\) 出发，设一条路径的长度是路径中经过点的个数减一。求所有从 \((1,1)\) 出发的路径中，路径长度的最大值。

输入格式

第一行两个正整数 \(n,m\) ，表示网格的大小。

接下来 \(n\) 行每行 \(m\) 个整数。

输出格式

一行一个整数，表示最长路径的长度。

样例输入

3 3
1 100 10000
15 140 10000 
30 -50 0

样例输出

3

样例解释

其中一条路径如下：\((1,1)\to (2,1)\to (2,2)\to (2,3)\)

可以证明，这是从\((1,1)\)出发的最长的路径

样例输入2

3 3
1 2 3
8 9 4
7 6 5

样例输出2

8

样例输入3

17 15
-9875871 2968753 6062656 -9487956 -9451249 -9417777 -9360224 -9159027 -8970025 -8952548 -4757890 -691849 -8750462 -8690543 4267992 
-8593033 -8477536 -8426596 -8348504 5914883 7855935 -8099409 -8070048 -8054774 -930761 -7949957 -7871272 -7866213 -7856019 -7671457 
-1930023 -7558500 -7428402 -7391117 -7298916 3835886 -7226299 -7033009 -6988569 9001353 -6342652 -3026734 -6219984 -3529860 -6172526 
-6084598 -6059457 -6022585 -5995894 -5891205 -5654663 -5615680 -5563767 -5422989 -5369141 5618482 -5221450 8188817 -5141903 -566925 
-8816032 -4756358 4023496 -8789394 -4636075 9081727 -4484068 -4314013 -4294001 -4259589 -4246825 -4231126 -4228841 -4157910 -4120290 
-3927768 -3912492 7724922 840088 -3571194 -3552781 -6189059 -3497221 -2846734 -3408058 -3315581 -3298587 -3142446 -3141664 -3122973 
-3047581 -3044587 -3035352 -6283060 -2996103 -2902959 9808820 3225647 -2814858 -2762584 -2619564 -2473814 -2391364 -2360743 -2304716 
-3874983 -2233753 -2156530 -2155582 2993363 -1996049 7742472 -1737712 -1667351 -1636381 -1197342 7780320 -959645 -7988547 -894135 
-846778 -765765 -4737975 -750270 864071 -653913 -4945990 -544778 -538194 -9549609 -421387 -327498 -283557 -265533 -237798 
6239560 -43494 2162743 169070 591547 677746 783018 -3648156 -4655730 866590 942511 1022018 2938595 1161792 1298839 
1419861 1675912 1796137 1896325 2105852 6660081 2213950 2455191 2472165 2492044 2509720 8701950 2674921 2710722 -752777 
2874723 2911808 2928376 3762945 2963665 -9778021 4406374 -3484937 3257123 3298623 3305845 3332351 3336772 3721223 1107422 
3805350 -7249129 3933141 -5340041 4093856 4154185 4172940 4239639 4244569 -8670406 -2122672 4449001 4499355 4701768 -1108892 
4931579 5060283 5088011 5239380 5397673 5414442 5442509 2827623 5831115 5913875 -8338223 5915389 5970975 6033035 6047804 
-464463 6112031 6222738 -227266 6302382 6345521 6359354 6366720 6506438 63753 6687254 6810079 9673629 7084761 7215379 
7295996 7336171 7472809 7522177 7609336 7679586 -2274241 -7664403 4794049 7817692 7836960 -8142646 7998172 8103696 -5164597 
8297198 8322021 2568485 8771553 8872516 8901798 -6396502 -4520306 9311648 9509229 6818568 9763929 9793455 -2880992 9885542 

样例输出3

30

数据范围及限制

网格中的数字 \(-10^7\le a_{ij}\le 10^7\)

测试点编号	\(n,m\)	测试点分值
1~5	\(n=1\) ，\(2\le m\le 20\)	每个测试点10分
6~11	\(2\le n,m\le 20\)	每个测试点15分
12~14	\(2\le n,m\le 500\)	每个测试点20分