글 읽기 - 반례를 못찾겠습니다ㅠ

chowg1762 2년 전 0

계속 43%정도에서 틀렸다고 하는데 반례를 정말 못찾겠습니다ㅠㅠ
도와주시면 감사하겠습니다
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int N;
    static int M;
    static int H;

    //0 => no line 1 => has a line
    static int[][] map;
    static ArrayList<LineM> initLines = new ArrayList<>();
    static int Lines = Integer.MAX_VALUE;
    static boolean LineSet = false;
    static ArrayList<LineM> lineQueues = new ArrayList<>();

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        N  = input.nextInt();
        M = input.nextInt();
        H = input.nextInt();
        map = new int[H][N];
        for(int r=0; r<H; r++){
            for(int c=0; c<N; c++)
                map[r][c] = 0;
        }

        //The ladder starts with 1, but the map starts with 0. So I subtract 1 from map's n index
        //init ladders
        for(int i=0; i<M; i++){
            int r = input.nextInt();
            int c = input.nextInt();
            map[r-1][c-1] = 1;
            initLines.add(new LineM(r-1,c-1));
        }

        if(M==0 || M==H*(N-1) ) {
            boolean result = exploreLadders();
            if(result == true)
                System.out.println(0);
            else
                System.out.println(-1);
            return;
        } else{
            boolean result = exploreLadders();

            if(result == true) {
                System.out.println(0);
                return;
            }
        }

        //Init Queue
        for(int r=0; r<H; r++) {
            for (int c = 0; c < N-1 ; c++) {
                if (map[r][c] == 0) {
                    if((c>0 && map[r][c-1]==0)&&(c<N-1 && map[r][c+1]==0)){
                        lineQueues.add(new LineM(r, c));
                    } else if(c==0 && map[r][c+1]==0){
                        lineQueues.add(new LineM(r, c));
                    }
                }
            }
        }

        for(int i=1; i<= lineQueues.size(); i++) {
            // i lines added
            if(i>3){
                break;
            }

            install(i, 0);

            if(LineSet) {
                break;
            }
        }

        if(LineSet && Lines>3 || Lines==Integer.MAX_VALUE){
            Lines = -1;
        }

        System.out.println(Lines);
    }

    public static void install(int numOfLines, int currentLineIndex){
        if(currentLineIndex>=numOfLines){

            if(exploreLadders()) {
                Lines = numOfLines;
                LineSet = true;
            }

            return;
        }

        for(int i=currentLineIndex; i<lineQueues.size(); i++){
            //LineM addedLine = localQ.remove(0);
            LineM currentLine = lineQueues.get(i);

            if(currentLine.c1==0||currentLine.c1>0&&map[currentLine.r1][currentLine.c1-1]==0) {
                map[currentLine.r1][currentLine.c1] = 1;
                install(numOfLines, currentLineIndex+1);
                map[currentLine.r1][currentLine.c1] = 0;
            }

            if(LineSet) {
                break;
            }
        }

    }

    public static boolean exploreLadders(){


        for(int i=0; i<N; i++){
            int currentH = 0;
            int currentN = i;

            while(currentH<H){
                //move horizontal
                if(map[currentH][currentN]==1) {
                    currentN += 1;
                } else {
                    if(currentN>0&&map[currentH][currentN-1]==1) {
                        currentN -= 1;
                    }
                }
                //move down
                currentH+=1;
            }

            if(i!=currentN) {
                return false;
            }
        }


        return true;
    }

}

class LineM {
    int r1;
    int c1;

    public LineM(int r1, int c1) {
        this.r1 = r1;
        this.c1 = c1;
    }
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례를 못찾겠습니다ㅠ

chowg1762 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말
