下面是一个例子12345161718196152425207142322218131211109一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小.在上面的例子中,一条可滑行的滑坡为24-17-16-1.当然25-24-23-

Question

下面是一个例子
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
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小.在上面的例子中,一条可滑行的滑坡为24-17-16-1.当然25-24-23-...-3-2-1更长.事实上,这是最长的一条.
01.#include
02.#include
03.#include
04.usingnamespacestd;
05.intopt[102][102];
06.intmap[102][102];
07.intdir[4][2] ={-1,0,1,0,0,-1,0,1};
08.intr,c;
09.intw(inta,intb)
10.{
11.inti;
12.if(ac)return0;
13.if(opt[a][b] = 0) returnopt[a][b];
14.else
15.{
16.for(i=0;i opt[a][b] )
19.opt[a][b]=w(a+dir[i][1],b+dir[i][0]);
20.return ++opt[a][b];
21.}
22.}
23.intmain(void)
24.{
25.intmax,i,j;
26.intn;
27.scanf("%d",&n);
28.while(n--)
29.{
30.scanf("%d%d",&r,&c);
31.for( i = 1 ; i

Answer 1

通过动态规划来寻找一条最长的路线的长度
假设f(r, c)表示现在处在第r行第c列时能够进行的最长路线的长度
那么f(r, c) = 1 + max(f(r-1, c), f(r+1, c), f(r, c-1), f(r, c+1)) 即1加上四个方向的最大长度
根据上面的定义可以写出一个backtracking算法解决,这里用动态规划来提高效率
上面算法的数组opt存放的f(r, c),首先其初始化为0, 34-35行
13行检查是否已经计算过f(a, b),有则可直接返回
14-24行即根据上面讲的计算f(r, c)的方法计算f(a, b)
dir 是一个lookup table用来存放四个方向dr, dc值.
16行的for循环检查四个方向
17行确定检查的地点的值是小于当前地点的值（根据滑动要求）
18,19行就是求四个方向的最大值,并将它存储到opt[a][b]中
20行加一得到最后的值
这个函数终止可以从当前点的值看出来,每一次调用,当前点的值都减小,可以从17行看出
最终a,b小于0,函数返回
上面的解释不好理解可以将这个问题看得更一般一些,将想成一个search problem来理解
那么这个函数实际上就是一个算法来找一个state到另一个state的最大路线的长度.