dfs深度搜索入门之滑雪

P1434 [SHOI2002] 滑雪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题我们主要使用了深度搜索和记忆化搜所。

首先我们可从任意一点开始滑行，这要求我们每一个点都进行一次深搜。但是如果每个点进行的话肯定会有许多个点重复被寻找最长滑雪长度，怎么办呢？这就轮到记忆化搜所了。我们每找到一个点就把这个点的最长化学长度保存起来。具体原理，我放在代码注释中。

public static int[][] aa;//每个点的高度
public static int bb;
public static int cc;
public static int[][] record;//记录任意一点得到最大化学长度
public static boolean[][] visited;//记录这一点有没有被探索过
public static int[] xx= {-1,1,0,0};///枚举位置
public static int[] yy= {0,0,-1,1};
public static int dfs(int a,int b) {if(visited[a][b]==true) {///如果一个点我们之前已经搜索过了直接返回这个点的最大滑雪长度return record[a][b];}int answer=0;record[a][b]=1;//若这个点没被探索过，我们先把其赋值为1因为任意一点滑雪长度至少是他自己就是1visited[a][b]=true;//接下来开始搜索这个点，先提前标记为·1int c;for(c=0;c<4;c++) {//往这个点的四个方位搜索int x=xx[c]+a;int y=yy[c]+b;if(x<0||x>=bb||y<0||y>=cc) {continue;}if(aa[a][b]>aa[x][y]) {//找到这四个方位最大长度answer=Math.max(answer, dfs(x, y));}}record[a][b]= record[a][b]+answer;加上去return record[a][b];
}}

完整代码：

import java.awt.FontFormatException;
import java.io.BufferedReader; 
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.AnnotatedWildcardType;
import java.math.BigInteger;
import java.net.DatagramPacket;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Spliterator.OfPrimitive;
import java.util.function.IntToDoubleFunction;
import java.util.function.LongBinaryOperator;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.management.relation.InvalidRelationTypeException;
import javax.print.attribute.standard.JobMessageFromOperator;
import javax.print.attribute.standard.JobPriority;
import javax.swing.plaf.ColorChooserUI;
import javax.swing.table.TableModel;
import javax.swing.text.TabSet;
import javax.xml.crypto.dsig.spec.DigestMethodParameterSpec;
public class Main {public static void main(String[] args) throws IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br1.readLine().split(" ");
bb=Integer.parseInt(aStrings[0]);
cc=Integer.parseInt(aStrings[1]);
aa=new int[bb+1][cc+1];
record=new int[bb+1][cc+1];
visited=new boolean[bb+1][cc+1];
int a,b;
for(a=0;a<bb;a++) {String[] bStrings=br1.readLine().split(" ");for(b=0;b<cc;b++) {aa[a][b]=Integer.parseInt(bStrings[b]);}
}
int ans=0;for(a=0;a<bb;a++) {for(b=0;b<cc;b++) {ans=Math.max(ans, dfs(a, b));}
}
System.out.println(ans);
}
public static int[][] aa;
public static int bb;
public static int cc;
public static int[][] record;
public static boolean[][] visited;
public static int[] xx= {-1,1,0,0};
public static int[] yy= {0,0,-1,1};
public static int dfs(int a,int b) {if(visited[a][b]==true) {return record[a][b];}int answer=0;record[a][b]=1;visited[a][b]=true;int c;for(c=0;c<4;c++) {int x=xx[c]+a;int y=yy[c]+b;if(x<0||x>=bb||y<0||y>=cc) {continue;}if(aa[a][b]>aa[x][y]) {answer=Math.max(answer, dfs(x, y));}}record[a][b]= record[a][b]+answer;return record[a][b];
}}