POJ 1088 skiing

http://poj.org/problem?id=1088

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 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更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

http://java-mans.iteye.com/blog/1640564

定义 m[i][j] 表示从点 (i,j) 为起点滑行的最大长度。滑行时，选择周围可以滑行的且 m 值最大的方向滑行。如果 (i,j) 的四个相邻元素都存在的话，则可以得到如下递归式：

m[i][j]=Max(m[i][j-1],m[i][j+1],m[i-1][j],m[i+1][j]) +1

通过递归地计算 m[i][j-1],m[i][j+1],m[i-1][j] 和 m[i+1][j] 的值，找中四个中最大的一个，即是下一步滑行的位置，以此递归，直到不能继续滑行时返回。求解过程中，每求解到一个点的最大滑行长度则保存在数组m[i][j]中，因此不会重复求解同一个点的最大滑行长度。

const int x[]={-1,0,1,0},y[]={0,1,0,-1}; //巧妙之处

int r,c;

int node[101][101];

int ppt[101][101];

//深搜

int dfs(int i,int j)

{

int k;

if(ppt[i][j]) //不为0，说明被访问过，直接返回

return ppt[i][j];

for(k=0;k<4;k++)//k值是为了决定x和y的方向(上下左右)

if(i+x[k]>=1 && i+x[k]<=r && j+y[k]>=1 && j+y[k]<=r) //没有越界

if( node[i+x[k]][j+y[k]]<node[i][j] ) //周围某点(上下左右之一,看循环的值了)高度小于当前点

if( ppt[i][j]< dfs(i+x[k],j+y[k])+1 ) //当前点的最大滑雪长度小于等于周围某点

ppt[i][j]=dfs(i+x[k],j+y[k])+1; //更改当前点的最大滑雪长度

return ppt[i][j];

}

http://www.douban.com/note/209925117/
bool ok(int i,int j)
{
  return (i>=1 && i<=r && j>=1 &&j<=c);
}

int dp(int i,int j)
{
    int k;
    if(opt[i][j]>0) return opt[i][j]; //如果已经计算出,直接返回
    for(k=0;k<4;k++) //向四个方向延伸
    {
        if(ok(i+dx[k],j+dy[k])) //如果节点没有超出边界
            if( node[i+dx[k］[j+dy[k］<node[i][j] ) //满足滑雪条件
            {
                if( opt[i][j]< dp(i+dx[k],j+dy[k])+1 )
                         opt[i][j]=dp(i+dx[k],j+dy[k])+1;
            }
    }
    return opt[i][j];
}
http://www.cnblogs.com/yrbbest/p/5126855.html

这是POJ经典的记忆化搜索结构题目，给定一个二维矩阵里，找到一条最长的下降坡道（4-connected，从最大值到最小值为递减的一条path）。

我们主要可以维护一个count[][]矩阵，对上下左右分别用dfs来记录下每个位置的最大count。之后也要做一些pruning，比如当count[i][j] > 0的时候，表示这个位置已经被计算过，可以直接返回count[i][j]来省略重复计算。 

public class Solution {
    private int[][] count;
    
    public int findDownHillSki(int[][] board) {        
        count = new int[board.length][board[0].length];        // matrix count for counting        
        int max = 0;
        for (int i = 0; i < board.length; i++) {            // fill count[][] using findMax(i, j, board)
            for (int j = 0; j < board[0].length; j++) {
                findMax(i, j, board);
                max = Math.max(max, count[i][j]);
            }
        }        
        return max;
    }
    
    private int findMax(int i, int j, int[][] board) {
        int max = 0;
        if (count[i][j] > 0) {
            return count[i][j]; 
        }
        
        if (i - 1 >= 0) {
            if (board[i][j] > board[i - 1][j]) {                
                max = Math.max(max, findMax(i - 1, j, board));
            }
        }
        if (j - 1 >= 0) {
            if (board[i][j] > board[i][j - 1]) {                
                max = Math.max(max, findMax(i, j - 1, board));
            }
        }
        if (i + 1 < count.length) {
            if (board[i][j] > board[i + 1][j]) {                
                max = Math.max(max, findMax(i + 1, j, board));
            }
        }
        if (j + 1 < count[0].length) {
            if (board[i][j] > board[i][j + 1]) {                
                max = Math.max(max, findMax(i, j + 1, board));
            }
        }
        return count[i][j] = max + 1;
    }
}

http://lyeec.me/blog/POJ/POJ-1088/
用逆向思维，从低的点取值取到高的点。这样就不会漏掉状态了。
用f[i][j]表示点(i,j)出发到可以到达的最高的点的距离。
所以搜索点(i,j)的时候，先搜索它周围的四个点，用它周围的四个点的f值更新(i,j)的f值。
也就是说如果h(i,j)<h(i±1,j±1)
那么f(i,j)=max(f(i,j),f(i±1,j±1)+1)

int f[200][200], h[200][200];
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int r, c;
int max(int a, int b) { return a > b ? a : b;}
int find(int, int);
int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            scanf("%d", &h[i][j]);
    int ans = 0;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            ans = max(ans, find(i,j));
    printf("%d", ++ans);
}
int find(int x, int y) {
    if(x < 0 || y < 0 || x >= r || y >= c) return 0;
    if(f[x][y] > 0)  return f[x][y];
    for (int i = 0; i < 4; i++)
        if(h[x + dx[i]][y + dy[i]] > h[x][y])
            f[x][y] = max(f[x][y], find(x + dx[i], y + dy[i]) + 1);
    return f[x][y];
}

X. BFS
http://my.oschina.net/Alexanderzhou/blog/203111
设一与输入数组对应的状态数组 dp，其值代表输入数组中此点的最长滑雪路径。使用广搜填表，最后遍历输出最大值即可。
const int MAX = 100; int map[MAX][MAX]; int dp[MAX][MAX]; int r, c; int BFS(int i, int j) { int max = -1; // 如当前坐标右侧有路，则广搜填值 if (j + 1 < c && map[i][j] > map[i][j + 1]) { if (dp[i][j + 1]) { max = max > dp[i][j + 1] ? max : dp[i][j + 1]; } else { max = max > BFS(i, j + 1) ? max : BFS(i, j + 1); } } // 向下广搜 if (i + 1 < r && map[i][j] > map[i + 1][j]) { if (dp[i + 1][j]) { max = max > dp[i + 1][j] ? max : dp[i + 1][j]; } else { max = max > BFS(i + 1, j) ? max : BFS(i + 1, j); } } // 向左广搜 if (j - 1 >= 0 && map[i][j] > map[i][j - 1]) { if (dp[i][j - 1]) { max = max > dp[i][j - 1] ? max : dp[i][j - 1]; } else { max = max > BFS(i, j - 1) ? max : BFS(i, j - 1); } } // 向上广搜 if (i - 1 >= 0 && map[i][j] > map[i - 1][j]) { if (dp[i - 1][j]) { max = max > dp[i - 1][j] ? max : dp[i - 1][j]; } else { max = max > BFS(i - 1, j) ? max : BFS(i - 1, j); } } // 如上下左右均不通，该点路径值为 1； // 否则取最大路径值加 1 if (max == -1) { dp[i][j] = 1; } else { dp[i][j] = 1 + max; } return dp[i][j]; } int solve() { // 遍历所有坐标，不留死角 int ans = 0; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { // 如尚未寻访此点，从此点向四面广搜 if (!dp[i][j]) { BFS(i, j); } // 同时记录最长路径 if (dp[i][j] > ans) { ans = dp[i][j]; } } } return ans; }
http://www.skymoon.biz/poj-1088%E9%A2%98-%E6%BB%91%E9%9B%AA/?variant=zh-tw

05	int a[101][101],dp[101][101],n,m,x,y;

06	int b[4][2]={-1,0,1,0,0,-1,0,1};

07	int bfs(int x,int y)

08	{   int s,t,max1;

09	if(dp[x][y]>1)return dp[x][y];

10	for(int l=0;l<4;l++)

11

{

12	s=x+b[l][0];t=y+b[l][1];

13	if(s>=0&&s<n&&t>=0&&t<m&&a[x][y]<a[s][t])

14	{    max1=bfs(s,t);

15	if((max1+1)>dp[x][y])

16	dp[x][y]=max1+1;

17

}

18

}

19	return dp[x][y];

20

}

21	int main()

22

{

23	int T,i,j,k,l;

24	while(~scanf("%d%d",&n,&m))

25	{memset(a,0,sizeof(a));

26	for(i=0;i<n;i++)

27	for(j=0;j<m;j++)

28	{   scanf("%d",&a[i][j]);dp[i][j]=1;}

29	int max=0;

30	for(i=0;i<n;i++)

31	for(j=0;j<m;j++)

32

{

33

bfs(i,j);

34	if(dp[i][j]>max)

35	max=dp[i][j];

36

}

37	printf("%d\n",max);

38	}return 0;

39

}

X. Greedy
 https://github.com/mccxj/codelab/blob/master/src/main/java/org/poj/Main1088.java
 * 方法1: 对所有位置的高度从小到大进行排序,从高度低的位置开始,计算它的最长滑雪路径(找周围高度比它小并且路径最长的,加1即可).
 * 使用贪心法,就可以计算出所有位置的最长滑雪路径,再从中找到个最大的就是结果.
     private static void run1() {
        Scanner cin = new Scanner(System.in);
        int r = cin.nextInt();// 行数
        int c = cin.nextInt();// 列数

        List<int[]> heights = new ArrayList<int[]>();// 用于对高度进行排序
        int[][] hs = new int[r][c];// 保留当前位置的最长滑雪路径
        int[][] hss = new int[r][c];// 保留当前位置的高度
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                hs[i][j] = 0;
                int h = cin.nextInt();
                hss[i][j] = h;
                heights.add(new int[]{h, i, j});
            }
        }

        // 对高度进行从小到大排序
        Collections.sort(heights, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int mm = 1;
        for (int[] xx : heights) {
            int rr = xx[1];
            int cc = xx[2];
            int max = 0;

            // 找周围高度比它小并且路径最长的
            if (rr - 1 >= 0 && xx[0] > hss[rr - 1][cc] && hs[rr - 1][cc] > max)
                max = hs[rr - 1][cc];
            if (cc - 1 >= 0 && xx[0] > hss[rr][cc - 1] && hs[rr][cc - 1] > max)
                max = hs[rr][cc - 1];
            if (rr + 1 < r && xx[0] > hss[rr + 1][cc] && hs[rr + 1][cc] > max)
                max = hs[rr + 1][cc];
            if (cc + 1 < c && xx[0] > hss[rr][cc + 1] && hs[rr][cc + 1] > max)
                max = hs[rr][cc + 1];
            hs[rr][cc] = max + 1;// 更新当前位置的最长滑雪路径
            // 顺便记录当前环境下的最长路径
            if (hs[rr][cc] > mm)
                mm = hs[rr][cc];
        }
        System.out.println(mm);
    }
http://blog.csdn.net/enigma_hao/article/details/9183381

• 先对数组中的数据进行排序，从最小的数据计算 当前的顶点的可以滑行的最大值=max（周围可达的顶点的可以滑行的最大值）+1
• 这样计算最后产生的路径肯定是最大的