记忆化搜索——滑雪

女爷i 2022-08-21 01:20 192阅读 0赞

Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 87592 Accepted: 32835  
Description

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

输出最长区域的长度。  
Sample Input

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  
Sample Output

25  
Source

刚开始用深搜做的，当输入测试样例时，虽然答案正确了，但运行时间却已超出了题目限制。

//DFS
    import java.util.Scanner;
    
    public class Main {
    
        public static int R,C;
        public static boolean DEBUG = true;
        public static int[] dirx = {-1,1,0,0},diry={
       0,0,-1,1}; 
        public static int[][] grids = new int[110][110];
        public static int[][] rec = new int[110][110];
    
        public static void init(){
            for(int i=0;i<110;i++){
                for(int j=0;j<110;j++){
                    rec[i][j] = -1;
                }
            }
        }
        public static void test(){
            System.out.println("test!");
        }
        public static void show1(){
            System.out.println("grids output:");
            for(int i=0;i<R;i++){
                for(int j=0;j<C;j++) System.out.print(grids[i][j]+" ");
                System.out.println();
            }
        }
    // public static void show2(){ 
    // for(int i=0;i<R;i++){ 
    // for(int j=0;j<C;j++){ 
    // for(int k=0;k<R*C;k++) System.out.println();
    // }
    // }
    // }
        public static int DFS(int x,int y,int step){
            int nx,ny,v = grids[x][y];
            int ret = step;//走到(x,y)所需的步数，如果不能再走了，就直接返回。
            for(int i=0;i<4;i++){
                nx = x+dirx[i];
                ny = y+diry[i];
                if(nx>=0&&nx<R&&ny>=0&&ny<C&&v>grids[nx][ny]){
                    int t = DFS(nx, ny, step+1);
                    if(ret<t) ret = DFS(nx, ny, step+1);
                }
            }
            return ret;
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                R = in.nextInt();
                C = in.nextInt();
                for(int i=0;i<R;i++){
                    for(int j=0;j<C;j++) grids[i][j] = in.nextInt();
                }
                init();
                long t1 = System.currentTimeMillis();
                int res = -1,t;
                for(int i=0;i<R;i++){
                    for(int j=0;j<C;j++){
                        t = DFS(i,j,1);//表示从(i,j)处出发可以搜索到的最大长度
                        if(res<t) res = t;
                    }
                }
                System.out.println(res);
                long t2 = System.currentTimeMillis();
                System.out.println("Time cost:"+(t2-t1));
            }
        }
    
    }

考虑了一下递归的状态树，发现有很多重复的状态，自然而然的想到了记忆化搜索，然后ＡＣ

import java.util.Scanner;
    
    public class Main {
    
        public static int R,C;
        public static boolean DEBUG = true;
        public static int[] dirx = {-1,1,0,0},diry={
       0,0,-1,1}; 
        public static int[][] grids = new int[110][110];
        public static int[][] rec ;
    
        public static void init(){
            int line = (R+1)*(C+1);
            for(int i=0;i<R;i++){
                for(int j=0;j<C;j++){
                     rec[i][j]= -1;
                }
            }
        }
        public static int DFS(int x,int y){
            if(rec[x][y]!=-1) return rec[x][y];
            int nx,ny,v = grids[x][y];
            int ret = 0;//走到(x,y)所需的步数，如果不能再走了，就直接返回。
            for(int i=0;i<4;i++){
                nx = x+dirx[i];
                ny = y+diry[i];
                if(nx>=0&&nx<R&&ny>=0&&ny<C&&v>grids[nx][ny]){
                    int t = DFS(nx, ny);
                    if(ret<t) ret = t;
                }
            }
            return rec[x][y]=ret+1;//累加的长度在这儿体现，加1
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                R = in.nextInt();
                C = in.nextInt();
                rec = new int[R][C];
                for(int i=0;i<R;i++){
                    for(int j=0;j<C;j++) grids[i][j] = in.nextInt();
                }
                init();
                long t1 = System.currentTimeMillis();
                int res = -1,t;
                for(int i=0;i<R;i++){
                    for(int j=0;j<C;j++){
                        t = DFS(i,j);//表示从(i,j)处出发可以搜索到的最大长度
                        if(res<t) res = t;
                    }
                }
                System.out.println(res);
                long t2 = System.currentTimeMillis();
                //System.out.println("Time cost:"+(t2-t1));
            }
        }
    }

注意备忘录rec\[x\]\[y\]存储的是点(x,y)可以走到的最大步数，之前rec已全部初始化为-1，用于标记。所以在搜索过程中一旦，搜索到(x,y)处，发现其值不为-1，直接返回即可。