网站建设资金预算,wordpress如何访问量,温州做网站的公司有哪些,小百姓网免费发布信息网P1434 [SHOI2002] 滑雪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
本题我们主要使用了深度搜索和记忆化搜所。
首先我们可从任意一点开始滑行#xff0c;这要求我们每一个点都进行一次深搜。但是如果每个点进行的话肯定会有许多个点重复被寻找最长滑雪长度#xff0c;…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 answer0;record[a][b]1;//若这个点没被探索过我们先把其赋值为1因为任意一点滑雪长度至少是他自己就是1visited[a][b]true;//接下来开始搜索这个点先提前标记为·1int c;for(c0;c4;c) {//往这个点的四个方位搜索int xxx[c]a;int yyy[c]b;if(x0||xbb||y0||ycc) {continue;}if(aa[a][b]aa[x][y]) {//找到这四个方位最大长度answerMath.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 scnew Scanner(System.in);
BufferedReader br1new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1new PrintWriter(System.out);
String[] aStringsbr1.readLine().split( );
bbInteger.parseInt(aStrings[0]);
ccInteger.parseInt(aStrings[1]);
aanew int[bb1][cc1];
recordnew int[bb1][cc1];
visitednew boolean[bb1][cc1];
int a,b;
for(a0;abb;a) {String[] bStringsbr1.readLine().split( );for(b0;bcc;b) {aa[a][b]Integer.parseInt(bStrings[b]);}
}
int ans0;for(a0;abb;a) {for(b0;bcc;b) {ansMath.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 answer0;record[a][b]1;visited[a][b]true;int c;for(c0;c4;c) {int xxx[c]a;int yyy[c]b;if(x0||xbb||y0||ycc) {continue;}if(aa[a][b]aa[x][y]) {answerMath.max(answer, dfs(x, y));}}record[a][b] record[a][b]answer;return record[a][b];
}}
