글 읽기 - 진짜 반례를 모르겠습니다...

2014136088 1년 전 0

게시판에 있는 반례는 싹 다 돌려본것 같은데 문제가 없어요....

능력자분들 반례 좀 찾아주시면 감사하겠습니다 ㅜㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static class Number {
        int numVal;
        String commands;

        public Number(int numVal, String commands) {
            this.numVal = numVal;
            this.commands = commands;
        }
    }
    public static int start, end;
    public static String answer;
    public static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int TC = Integer.parseInt(br.readLine());

        for (int t = 0; t < TC; t++) {
            st = new StringTokenizer(br.readLine());

            answer = "";
            visit = new boolean[10000];
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());

            BFS(new Number(start, ""));

            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
    public static void BFS(Number n) {
        Queue<Number> queue = new LinkedList<>();

        queue.add(n);
        visit[n.numVal] = true;

        while(!queue.isEmpty()) {
            Number number = queue.poll();

            for (int i = 1; i <= 4; i++) {
                Number newNumber = simulation(i, number);

                if(newNumber.numVal == end) {
                    answer = newNumber.commands;
                    return;
                }

                if(visit[newNumber.numVal]) continue;
                queue.add(newNumber);
                visit[newNumber.numVal] = true;
            }
        }
    }
    public static Number simulation(int n, Number number) {
        Number newNumber = new Number(number.numVal,  number.commands);
        String strVal = String.valueOf(newNumber.numVal);

        if(strVal.length() < 4) {
            for (int i = 0; i < 4 - strVal.length(); i++) {
                strVal = "0" + strVal;
            }
        }

        switch (n) {
            case 1:
                newNumber.commands += "D";
                newNumber.numVal = (newNumber.numVal * 2) % 10000;
                break;
            case 2:
                newNumber.commands += "S";
                newNumber.numVal = newNumber.numVal == 0 ? 9999 : newNumber.numVal - 1;
                break;
            case 3:
                newNumber.commands += "L";

                strVal = strVal.substring(1) + strVal.substring(0, 1);
                newNumber.numVal = Integer.parseInt(strVal);
                break;
            case 4:
                newNumber.commands += "R";

                strVal = strVal.substring(3) + strVal.substring(0, 3);
                newNumber.numVal = Integer.parseInt(strVal);
                break;
        }

        return newNumber;
    }
}

bamgoesn 1년 전 17

반례입니다.

12
5 0
0 7
9 0
47 63
26 60
60 50
32 38
98 366
5310 6
7519 2006
7579 4005
2720 8031

정답
RD
SDRDRDRDDSDR
SDSRSD
RSDLS
RSSRR
RSL
RSLSSSD
SRDLSD
DRSSR
SDDRS
SRDDSDR
DDRSRDDS

출력
LLLD
SDDLDDSDDDDLS
SDSLLLSD
LLLSDLS
LLLSSLL
LLLSL
DDDRDLLSD
SDSRSDL
RSLDLL
SDDLLLS
DRSSRSDDL
DDSLDDSDR

2014136088 1년 전 0

정말 감사합니다 ㅜㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

진짜 반례를 모르겠습니다...

2014136088 1년 전 0

bamgoesn 1년 전 17

2014136088 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말