白駿14890号:スロープロード







問題の説明

  • https://www.acmicpc.net/problem/14890
  • 長さL、高さ1の斜面が通るかどうか.
  • スロープは一定の条件下でしか配置できません.
  • 方法

  • 配列を入力する場合、斜線を配置できるかどうかを決定する方法が必要だと思います.
  • 勾配は2種類(上向きと下向き)あるので、条件によって異なる勾配を使用する必要があります.
  • スロープが使用できない条件を決定する必要があります.
  • の高さ差が2より大きいと、道路を渡ることができません.
  • 勾配が設定されている格子に勾配を再作成することはできません.
  • は、セルが傾いているかどうかを判断するv配列を作成します.
  • pseudocode

    Main(){
    	모든 행 배열과 열 배열에 대해 SlideCheck를 진행.
    }
    SlideCheck(배열){
    	for(i=0부터N-1까지){
        	if(i번째 값과 i+1번째 값이 2 이상 차이나면) return false
        	if(i번쨰 칸에 올라가는 경사로와 내려가는 경사로를 모두 놓아야 하는 상황이면) return false
            if(i번째 값보다 i+1번째 값이 1 크면){ // 올라가는 경사로가 필요하면
            	if(!UpSlideCheck) return false // 올라가는 경사로를 못놓으면 false
                올라가는 경사로를 놓을 수 있으면 해당 칸들을 중복사용 못하게 방문처리    
            }
            if(i번째 값보다 i+1번쨰 값이 1 작으면){ // 내려가는 경사로가 필요하면
            	if(!DownSlideCheck) return false // 내려가는 경사로를 못놓으면 false
            }        
        }
        return true //못놓는 경우를 모두 피해갔으면 해당 배열은 길로 지나갈 수 있음.
    }
    UpSlideCheck(){
    	if(놓아야 하는 곳이 배열 밖이면) return false;
        for(now를 포함한 왼쪽 L개의 블록을 검사하면서){
        	if(now블록과 숫자가 다르거나, 해당칸에 이미 블록이 놓여있으면) return false
        }
    }
    DownSlideCheck(){
    	if(놓아야 하는 곳이 배열 밖이면) return false;
        for(now를 포함한 오른쪽 L개의 블록을 검사하면서){
        	if(now블록과 숫자가 다르거나, 해당칸에 이미 블록이 놓여있으면) return false
        }
    }
    

    正解

    import java.util.*;
    
    public class Main {
    	static int N, L, Score;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		N = sc.nextInt();
    		L = sc.nextInt();
    		int[][] board = new int[N][N];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				board[i][j] = sc.nextInt();
    			}
    		}
    		for (int i = 0; i < N; i++) {
            	//열 배열을 구합니다
    			int[] colArr = new int[N];
    			for (int j = 0; j < N; j++) {
    				colArr[j] = board[j][i];
    			}
                // 행 배열 길을 건널 수 있는지 체크합니다.
    			if (SlideCheck(board[i]))
    				Score++;
                // 열 배열 길을 건널 수 있는지 체크합니다.
    			if (SlideCheck(colArr))
    				Score++;
    		}
    		System.out.println(Score);
    	}
    
    	public static boolean SlideCheck(int[] arr) {
    		boolean[] v = new boolean[N];
            // 해당 칸(i)과 다음 칸(i+1)의 값이 다른지 비교합니다.
    		for (int i = 0; i < N - 1; i++) {
            	// 2칸 이상 차이가 나면 길을 건널 수 없습니다.
    			if (Math.abs(arr[i] - arr[i + 1]) >= 2)
    				return false;
                // 내려가는 경사로와 올라가는 경사로를 동시에 요구하는 길은 결국 건널 수 없는 길입니다.
    			if ((i < N && arr[i] < arr[i + 1] && UpSlideCheck(arr, i, v))
    					&& (i > 0 && arr[i - 1] > arr[i] && DownSlideCheck(arr, i + 1, v))) {
    				return false;
    			}
                // 올라가는 경사로가 필요합니다.
    			if (arr[i] < arr[i + 1]) {
                	// 올라가는 경사로를 설치할 수 없다면 false를 반환합니다.
    				if (!UpSlideCheck(arr, i, v))
    					return false;
                    // 올라가는 경사로를 설치했다면 해당 칸들에는 더 이상 경사로를 설치할 수 없습니다.
    				for (int j = i - L + 1; j <= i; j++) {
    					v[j] = true;
    				}
    			}
                // 내려가는 경사로가 필요합니다.            
    			if (arr[i] > arr[i + 1]) {
                	// 내려가는 경사로를 설치할 수 없다면 false를 반환합니다.            
    				if (!DownSlideCheck(arr, i + 1, v))
    					return false;
                    // 내려가는 경사로를 설치했다면 해당 칸들에는 더 이상 경사로를 설치할 수 없습니다.
    				for (int j = i + 1; j <= i + 1 + L - 1; j++) {
    					v[j] = true;
    				}
    			}
    		}
    		return true;
    	}
    
    	public static boolean UpSlideCheck(int[] arr, int now, boolean[] v) {
    		// 배열의 범위를 벗어나면 경사로를 놓을 수 없습니다.
    		if (now - L + 1 < 0)
    			return false;
            // now를 포함한 왼쪽 L개의 블록이 모두 같은 값인지를 판단합니다.
    		int Std = arr[now];
    		for (int i = now - L + 1; i < now; i++) {
    			if ((arr[i] != Std) || v[i]) //블록값이 다르거나 해당칸에 이미 경사로를 놓았다면 길을 건널 수 없습니다.
    				return false;
    		}
    		return true;
    
    	}
    
    	public static boolean DownSlideCheck(int[] arr, int now, boolean[] v) {
    		// 배열의 범위를 벗어나면 경사로를 놓을 수 없습니다.
    		if (now + L - 1 >= N)
    			return false;
            // now를 포함한 오른쪽 L개의 블록이 모두 같은 값인지를 판단합니다.
    		int Std = arr[now];
    		for (int i = now; i <= now + L - 1; i++) {
    			if (arr[i] != Std || v[i]) //블록값이 다르거나 해당칸에 이미 경사로를 놓았다면 길을 건널 수 없습니다.
    				return false;
    		}
    		return true;
    
    	}
    }