首页 > 专题系列 > Java解POJ > POJ 1088 滑雪 [解题报告] Java
2013
11-09

POJ 1088 滑雪 [解题报告] Java

滑雪

问题描述 :

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

输入:

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

输出:

输出最长区域的长度。

样例输入:

5 5
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

样例输出:

25

解题代码:

方法(1)动态规则
import java.util.Scanner;
public class Main{
  private int h[][]=new int[101][101];
  private int m[][]=new int[101][101];
  private int r,c;

  private void init(){
    Scanner sc=new Scanner(System.in);
    r=sc.nextInt();
    c=sc.nextInt();     
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            h[i][j]=sc.nextInt();
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            m[i][j]=-1;
  }

  //递归获取从点(i,j)出发滑行的最大长度
  private int GetHigh(int i,int j){    
    if(m[i][j]!=-1)//如果m[i][j]的值已经被计算过了
      return m[i][j];
    else{
      int max=0;
      int temp;
      if(j>1)//(i,j)的左边
      {
        if(h[i][j]>h[i][j-1]){
            temp=GetHigh(i,j-1);
            if(max< temp)
                max=temp;
        }
      }
      if(j< c)//(i,j)的左边
      {
        if(h[i][j]>h[i][j+1]){
            temp=GetHigh(i,j+1);
            if(max< temp)
                max=temp;
        }
       }
       if(i>1)//(i,j)的上边
      {
        if(h[i][j]>h[i-1][j]){
            temp=GetHigh(i-1,j);
            if(max< temp)
                max=temp;
        }
       }
       if(i< r)//(i,j)的下边
       {
         if(h[i][j]>h[i+1][j]){
            temp=GetHigh(i+1,j);
            if(max< temp)
               max=temp;
         }
        }
        m[i][j]=max+1;//填充备忘录
        return m[i][j];
    }
}

 public int getMaxHeight(){
   int temp;
   int Max=-1;
   for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            temp=GetHigh(i,j);
            if(Max< temp)
                Max=temp;    
        }
    }
    return Max;
  }

  public static void main(String args[]){
    Main m=new Main();
    m.init();
    System.out.println(m.getMaxHeight());
 }
}

方法(2)
import java.util.Scanner;

public class Main {
 public static class Node {
  int heigth;
  int length;
  boolean visited;
 }
 public static int c;
 public static int r;
 public static int findLength(int x, int y, Node[][] record ){
  int right = 0, left = 0, up = 0, down = 0, max = 0, temp1 = 0, temp2 = 0;   //System.out.println("1");
  
  if ( record[x][y].visited == true )
   return record[x][y].length;
  record[x][y].visited = true;
  //right
   if ( x < c - 1 && record[x][y].heigth < record[x +1][y].heigth)
    right = 1 + findLength ( x + 1 , y, record);
   
  //left
   if ( x > 0 && record[x][y].heigth < record[x - 1][y].heigth )
    left = 1 + findLength ( x -1 , y , record);
   
  //down
   if ( y < r - 1)
    if ( record[x][y].heigth < record[x][y + 1].heigth )
     down = 1 + findLength (x , y + 1, record);
   
  //up
   if ( y > 0)
    if ( record[x][y].heigth < record[x][y - 1 ].heigth )
     up = 1 + findLength ( x , y -1 , record);
   
   temp1 = left > right ? left : right;
   temp2 = down > up ? down : up;
   max = temp1 > temp2 ? temp1 : temp2;
   
  record[x][y].length = max;
  return max;
  
 }
 public static void main (String [] args ){
  Node record[][];
  c = 0; r = 0;
  int i, j, max = 0, temp = 0;
  
  Scanner cin = new Scanner (System.in);
  
  c = cin.nextInt();
  r = cin.nextInt();
  
  record = new Node[c][r];
  
  for ( i = 0; i < c; i++)
   for ( j = 0; j < r; j++){
    record[i][j] = new Node();
    record[i][j].heigth = cin.nextInt();
    record[i][j].length = 0;
    record[i][j].visited = false; 
   }
  
  for ( i = 0; i < c; i++)
   for ( j = 0; j < r; j++){
    temp = findLength ( i, j, record);
    max =  max > temp ? max : temp;
   }
    
  System.out.println(max  + 1 );
  
 }
}

方法(3)
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    class Pos implements Comparable< Pos> {
        public Pos(int i, int j, int h) {
            this.i = i;
            this.j = j;
            this.height = h;
        }

        int i;
        int j;
        int height;

        public int compareTo(Pos p2) {

            return height - p2.height;
        }
    }

    public static void main(String[] args) {
        Main mm = new Main();
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();
        int col = scanner.nextInt();
        int[][] map = new int[row][col];
        int[][] result = new int[row][col];
        for (int i = 0; i < row; i++) {
            
            Arrays.fill(result[i], 1);
        }
        Pos[] ps = new Pos[row * col];
        int num = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                map[i][j] = scanner.nextInt();
                ps[num++] = mm.new Pos(i, j, map[i][j]);
            }
        }
        Arrays.sort(ps); // 从小到大排序
        int tempI, tempJ, currI, currJ;
       
        int resultMax = 0;
        for (int i = 0; i < ps.length; i++) {
            int max = 0;
            currI = ps[i].i;
            currJ = ps[i].j;

            tempI = currI - 1;
            if (tempI >= 0 && ps[i].height > map[tempI][currJ]) {
                max = Math.max(max, result[tempI][currJ]);
            }
            tempI = currI + 1;
            if (tempI < row && ps[i].height > map[tempI][currJ]) {
                max = Math.max(max, result[tempI][currJ]);
            }
            tempJ = currJ - 1;
            if (tempJ >= 0 && ps[i].height > map[currI][tempJ]) {
                max = Math.max(max, result[currI][tempJ]);
            }
            tempJ = currJ + 1;
            if (tempJ < col && ps[i].height > map[currI][tempJ]) {
                max = Math.max(max, result[currI][tempJ]);
            }
            max = max + 1;
            result[currI][currJ] = max;
            if (max > resultMax) {
                resultMax = max;
              //  System.out.println(resultMax);
            }

        }
       System.out.println(resultMax);

    }
}

  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。