글 읽기 - 나와있는 반례가 다 되는데 50%에서 통과가 안됩니다..ㅠ

mangbini 1년 전 0

3일동안 매달리고 있는데 안되네요ㅠㅠ 틀린 부분이 있거나 반례가 있다면 고수님들 도와주십쇼..!

import java.util.*;
import java.io.*;

//baekjoon 6549

class Main {
    static class Point {
        int x, y, dir;
        public Point(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
    static int W, H;
    static Point[] C;
    static char[][] map;
    static boolean[][] visit;
    static int[][] mirror;
    static int min;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new char[H][W];
        visit = new boolean[H][W];
        mirror = new int[H][W];
        min = Integer.MAX_VALUE;
        C = new Point[2];

        boolean flag = false;
        for(int i = 0; i < H; i++) {
            map[i] = br.readLine().toCharArray();
            for(int j = 0; j < W; j++) {
                if(map[i][j] == 'C') {
                    if(!flag) {
                        C[0] = new Point(i,j,0);
                        flag = true;
                    }
                    else C[1] = new Point(i,j,0);
                }
            }
        }
        bfs();
        System.out.println(mirror[C[1].x][C[1].y]);
    }
    public static void bfs() {
        Queue<Point> q = new LinkedList<>();
        visit[C[0].x][C[0].y] = true;
        mirror[C[0].x][C[0].y] = 0;
        int[] dx = {0,0,-1,1};
        int[] dy = {1,-1,0,0};

        for(int i = 0; i < 4; i++) {
            if(C[0].x+dx[i] >= 0 && C[0].x+dx[i] < H && C[0].y+dy[i] >=0 && C[0].y+dy[i] < W && map[C[0].x+dx[i]][C[0].y+dy[i]] != '*') {
                int tmpx = C[0].x+dx[i];
                int tmpy = C[0].y+dy[i];
                while(tmpx >= 0 && tmpx < H && tmpy >= 0 && tmpy < W && map[tmpx][tmpy] != '*' && !visit[tmpx][tmpy]) {
                    visit[tmpx][tmpy] = true;
                    q.offer(new Point(tmpx, tmpy, i));
                    mirror[tmpx][tmpy] = mirror[C[0].x + dx[i]][C[0].y + dy[i]];
                    tmpx += dx[i];
                    tmpy += dy[i];
                }
            }
        }

        while(!q.isEmpty()) {
            Point p = q.poll();
            int x = p.x;
            int y = p.y;
            int dir = p.dir;
            if(C[1].x == p.x && C[1].y == p.y) {
                min = Math.min(min, mirror[C[1].x][C[1].y]);
                continue;
            }

            for(int i = 0; i < 4; i++) {
                if(x+dx[i] >= 0 && x+dx[i] < H && y+dy[i] >=0 && y+dy[i] < W && map[x+dx[i]][y+dy[i]] != '*') {
                    //방문하지 않았을 경우
                    if(!visit[x+dx[i]][y+dy[i]]) {
                        int tmpx = x+dx[i];
                        int tmpy = y+dy[i];
                        visit[tmpx][tmpy] = true;
                        if (dir == i) {
                            mirror[x + dx[i]][y + dy[i]] = mirror[x][y];
                        }
                        else {
                            mirror[x + dx[i]][y + dy[i]] = mirror[x][y] + 1;
                        }
                        tmpx += dx[i];
                        tmpy += dy[i];
                        while(tmpx >= 0 && tmpx < H && tmpy >= 0 && tmpy < W && map[tmpx][tmpy] != '*' && !visit[tmpx][tmpy]) {
                            visit[tmpx][tmpy] = true;
                            q.offer(new Point(tmpx, tmpy, i));
                            mirror[tmpx][tmpy] = mirror[x + dx[i]][y + dy[i]];
                            tmpx += dx[i];
                            tmpy += dy[i];
                        }
                    }
                    //방문했을 경우
                    else {
                        int tmp;
                        if (dir == i) tmp = mirror[x][y];
                        else tmp = mirror[x][y] + 1;
                        //거울 수가 이전 거울 수보다 적거나 같을 경우
                        if (tmp <= mirror[x + dx[i]][y + dy[i]]) {
                            mirror[x + dx[i]][y + dy[i]] = tmp;
                            q.offer(new Point(x + dx[i], y + dy[i], i));
                         }                            
                    }
                }
            }
        }
    }
}

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

문제

문제

출처

ICPC

나와있는 반례가 다 되는데 50%에서 통과가 안됩니다..ㅠ

mangbini 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말