글 읽기 - 반례 찾아주세요

tiro25 2년 전 0

BFS로 접근했고

S -> C1 -> C2 와 S -> C2 -> C1 중 더 짧은 경로를 답으로 출력하려고했어요.

70퍼정도에서 틀렸다고 나왔습니다.

반례 부탁드려요.

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

class Main {

    static int n, m;
    static char[][] board;
    static boolean[][][] visited;
    static Point s;
    static Point c1, c2;

    static int d;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        input();
        int answer = Math.min(route(c1, c2), route(c2, c1));
        if(answer == (int)1e9) {
            answer = -1;
        }
        System.out.println(answer);
    }

    static int route(Point via, Point dst) {
        d = -1;
        int route1 = bfs(s, via), route2 = bfs(via, dst);
        if(route1 < 0 || route2 < 0) {
            return (int)1e9;
        }
        return route1+route2;
    }

    static int bfs(Point src, Point dst) {
        int depth = -1;
        visited = new boolean[n][m][4];
        Queue<Point> q = new LinkedList<>();
        q.offer(src);
        src.dir = d;
        if(d != -1) {
            src.visit();
        }
        while(!q.isEmpty()) {
            depth++;
            int size = q.size();
            while(size-- > 0) {
                Point cur = q.poll();
                if(cur.equals(dst)) {
                    d = cur.dir;
                    return depth;
                }
                for(int dir = 0; dir < 4; ++dir) {
                    if(cur.dir == dir) {
                        continue;
                    }
                    Point next = cur.next(dir);
                    if(!next.isIn() || next.visited() || next.canNotMove()) {
                        continue;
                    }
                    if(src.value() == 'S' && next.value() == 'C' && !next.equals(dst)) {
                        continue;
                    }
                    next.visit();
                    q.offer(next);
                }
            }
        }
        return -1;
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new char[n][m];
        for(int i = 0; i < n; ++i) {
            String tmp = br.readLine();
            for(int j = 0; j < m; ++j) {
                board[i][j] = tmp.charAt(j);
                if(board[i][j] == 'S') {
                    s = new Point(i, j, -1);
                } else if(board[i][j] == 'C') {
                    Point p = new Point(i, j, -1);
                    if(c1 == null) {
                        c1 = p;
                    } else {
                        c2 = p;
                    }
                }
            }
        }
    }

    static class Point {
        int x, y;
        int dir;

        public Point(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }

        boolean isIn() {
            return x>=0&&x<n&&y>=0&&y<m;
        }

        boolean visited() {
            return visited[x][y][dir];
        }

        boolean canNotMove() {
            return board[x][y]=='#';
        }

        Point next(int dir) {
            return new Point(x+dx[dir], y+dy[dir], dir);
        }

        char value() {
            return board[x][y];
        }

        public void visit() {
            visited[x][y][dir] = true;
        }

        @Override
        public boolean equals(Object o) {
            if(!(o instanceof Point))
                return false;
            Point p = (Point) o;
            return x == p.x && y == p.y;
        }
    }
}

yong6768 2년 전 2

3 3

.C.

S..

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

문제

문제

출처

ICPC

반례 찾아주세요

tiro25 2년 전 0

yong6768 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말