스키 OpenJBailian-1088 JAVA 기억 화 검색 이 중요 합 니 다.

E-스키
 OpenJ_Bailian - 1088 
마 이 클 이 스키 백 을 좋아 하 는 것 은 이상 하지 않다.왜냐하면 스키 는 확실히 자극 적 이기 때문이다.그러나 속 도 를 얻 기 위해 서 는 미 끄 러 지 는 구역 이 아래로 기울 어야 하고,언덕 아래로 미 끄 러 지면 다시 언덕 을 올 라 가 거나 승강기 가 태 워 줄 때 까지 기 다 려 야 한다.마 이 클 은 한 지역 에서 가장 긴 슬로프 를 싣 고 싶 어 한다.구역 은 2 차원 배열 로 제 시 됩 니 다.배열 의 모든 숫자 대표 점 의 높이.다음은 하나의 예 이다.

 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

 
이 문 제 는 여러 번 고 쳐 서 많은 부분 을 제대로 이해 하지 못 했 습 니 다.특히 DFS 에 대해 서 는(예전 에 도 많이 만 났 습 니 다)너무 오래 연습 하지 않 아서 많은 문제 에 부 딪 혔 습 니 다.
1.DFS 와 BFS 는 반드시 사용 환경 을 구분 하고 BFS 의 vis 가 공용 이라는 것 을 알 아야 한다.
2.DFS 의 vis 는 true 이후 false 로 바 꿔 야 합 니 다.주의 하 세 요!수 정 된 vis 를 매개 변수 로 전달 할 수 없습니다.전 달 된 VIS(배열)는 주소 이기 때문에 새로운 DFS 에서 VIS 를 수정 한 후에 모든 vis 를 수정 하여 본 체 를 바 꾸 지 않 는 효과 에 이 르 지 못 합 니 다!
3.기억 화 검색,DFS 의 정의 와 DP 의 정의 에 주의
dp[i][j]는 바로 대 점 i,j 의 가장 먼 활주 경로 이다.0 이 되 지 않 으 면 반드시 성립 되 고 완전 하 다.
dfs(i,j),출력 은 dp[i][j]입 니 다.dp[i][j]가 모 를 때 만 사용 할 수 있 는 전략 입 니 다.
DFS 출력 은 영원히 dp[i][j]
 
AC 코드:(타고 난 방문 순서 가 있 기 때문에 arr[i][j]>arr[ti][tj]를 고려 하지 않 아 도 됩 니 다.중복 방문 은 걱정 하지 않 아 도 됩 니 다)

import java.util.Scanner;

public class Main{
	
	static int arr[][];
	static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
	static int x,y;
	static int dp[][];
//	static boolean vis[][];
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		x = sc.nextInt();
		y = sc.nextInt();
		arr = new int[x][y];
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		dp = new int[x][y];
		int max = -1;
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				max = Math.max(max, dfs(i,j));
			}
		}
		System.out.println(max);
		
	}
	private static int dfs(int i, int j) {
		if(dp[i][j]!=0) return dp[i][j];
		int ans = 0;
		for (int p = 0; p < dir.length; p++) {
			int xx = i+dir[p][0];
			int yy = j+dir[p][1];
			if(xx>=0&&yy>=0&&xx

시간 초과 코드:DFS+가지치기(팬)

import java.util.Scanner;

public class Main{
	
	static int arr[][];
	static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
	static int x,y;
	static int dp[][];
	static boolean vis[][];
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		x = sc.nextInt();
		y = sc.nextInt();
		arr = new int[x][y];
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		vis = new boolean[x][y];
		dp = new int[x][y];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[i].length; j++) {
				dp[i][j] = 1;
			}
		}
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				vis[i][j]=true;
				dfs(i,j,1);
				vis[i][j]=false;
			}
		}
		int max = -1;
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[i].length; j++) {
				if(max=0&&yy>=0&&xxarr[i][j]) {
					vis[xx][yy]=true;
					dfs(xx,yy,k+1);
					vis[xx][yy]=false;
				}
			}
		}
		dp[i][j] = Math.max(dp[i][j], k);
		return k;
	}
}	

최초의 어리석음(대량 중복 무효 작업)코드:(순수 DFS,시간 초과)

import java.util.Scanner;

public class Main{
	
	static int arr[][];
	static int ans = -1;
	static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
	static int x,y;
	
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		x = sc.nextInt();
		y = sc.nextInt();
		arr = new int[x][y];
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				boolean vis[][] = new boolean[x][y];
				vis[i][j] = true;	
				dfs(i,j,1,vis);
				vis=null;			//    ，    
				//  BFS，      VIS
//				q.clear();
//				q.add(new Node(2,2,1));
//				while(!q.isEmpty()) {
//					temp = q.poll();
//					vis[temp.x][temp.y] = true;
//					if(temp.l>ans) ans= temp.l;
//					for (int k = 0; k < dir.length; k++) {
////						System.out.println(temp.x+" "+temp.y+" "+dir[k][0]+" "+dir[k][1]);
//						xx = temp.x+dir[k][0];
//						yy = temp.y+dir[k][1];
//						if(xx>=0 && xx=0 && yyans) ans= k;
		for (int p = 0; p < dir.length; p++) {
			int xx = i+dir[p][0];		//new int!
			int yy = j+dir[p][1];
			if(xx>=0 && xx=0 && yy