글 읽기 - 있는 TC 전부 넣었습니다. 8% 반례도와주세요 ㅠㅠ

ckd5508 1년 전 2

거의 모든 TC를 넣고돌렸습니다 근데 어디 8% 까지만 가네요

도와주세요 ㅠㅠ

from collections import deque
import copy


def move(order, Map):
    rball = []
    bball = []
    for i in range(N):
        if 'R' in Map[i]:
            rball.append(i)
            rball.append(Map[i].index('R'))
        if 'B' in Map[i]:
            bball.append(i)
            bball.append(Map[i].index('B'))

    if order == 1:
        rnext = rball[0] - 1
        bnext = bball[0] - 1
        # 바뀐 공위치 구하기
        while 1:
            mv_cnt = 0
            if Map[bnext][bball[1]] == 'O':
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rnext][rball[1]] == 'O'and (bball[1] != rball[1]):
                mv_cnt += 1
                return 1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rnext][rball[1]] == 'O' and (bball[1] == rball[1]):
                if rball[0] > bball[0]:
                    return 1, Map, rball[0], rball[1], bball[0], bball[1]
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rnext][rball[1]] == '.':
                mv_cnt += 1
                Map[rnext][rball[1]], Map[rball[0]][rball[1]] = Map[rball[0]][rball[1]], Map[rnext][rball[1]]
                rball[0] -= 1
                rnext -= 1
            elif Map[bnext][bball[1]] == '.':
                mv_cnt += 1
                Map[bnext][bball[1]], Map[bball[0]][bball[1]] = Map[bball[0]][bball[1]], Map[bnext][bball[1]]
                bball[0] -= 1
                bnext -= 1
            if mv_cnt == 0:
                break

    if order == 2:
        rnext = rball[0] + 1
        bnext = bball[0] + 1
        # 바뀐 공위치 구하기
        while 1:
            mv_cnt = 0
            if Map[bnext][bball[1]] == 'O':
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rnext][rball[1]] == 'O' and (bball[1] != rball[1]):
                mv_cnt += 1
                return 1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rnext][rball[1]] == 'O' and (bball[1] == rball[1]):
                if rball[0] < bball[0]:
                    return 1, Map, rball[0], rball[1], bball[0], bball[1]
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rnext][rball[1]] == '.':
                mv_cnt += 1
                Map[rnext][rball[1]], Map[rball[0]][rball[1]] = Map[rball[0]][rball[1]], Map[rnext][rball[1]]
                rball[0] += 1
                rnext += 1
            elif Map[bnext][bball[1]] == '.':
                mv_cnt += 1
                Map[bnext][bball[1]], Map[bball[0]][bball[1]] = Map[bball[0]][bball[1]], Map[bnext][bball[1]]
                bball[0] += 1
                bnext += 1
            if mv_cnt == 0:
                break
    if order == 3:
        rnext = rball[1] - 1
        bnext = bball[1] - 1
        # 바뀐 공위치 구하기
        while 1:
            mv_cnt = 0
            if Map[bball[0]][bnext] == 'O':
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rball[0]][rnext] == 'O' and (bball[0] !=rball[0]):
                mv_cnt += 1
                return 1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rball[0]][rnext] == 'O' and (bball[0] ==rball[0]):
                if rball[1] >bball[1]:
                    return 1, Map, rball[0], rball[1], bball[0], bball[1]
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            if Map[bball[0]][bnext] == 'O':
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            if Map[rball[0]][rnext] == '.':
                mv_cnt += 1
                Map[rball[0]][rnext], Map[rball[0]][rball[1]] = Map[rball[0]][rball[1]], Map[rball[0]][rnext]
                rball[1] -= 1
                rnext -= 1
            if Map[bball[0]][bnext] == '.':
                mv_cnt += 1
                Map[bball[0]][bnext], Map[bball[0]][bball[1]] = Map[bball[0]][bball[1]], Map[bball[0]][bnext]
                bball[1] -= 1
                bnext -= 1
            if mv_cnt == 0:
                break
    if order == 4:
        rnext = rball[1] + 1
        bnext = bball[1] + 1
        # 바뀐 공위치 구하기
        while 1:
            mv_cnt = 0
            if Map[bball[0]][bnext] == 'O':
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rball[0]][rnext] == 'O' and (bball[0] != rball[0]):
                mv_cnt += 1
                return 1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rball[0]][rnext] == 'O' and (bball[0] == rball[0]):
                if rball[1] <bball[1]:
                    return 1, Map, rball[0], rball[1], bball[0], bball[1]
                mv_cnt += 1
                return -1, Map, rball[0], rball[1], bball[0], bball[1]
            elif Map[rball[0]][rnext] == '.':
                mv_cnt += 1
                Map[rball[0]][rnext], Map[rball[0]][rball[1]] = Map[rball[0]][rball[1]], Map[rball[0]][rnext]
                rball[1] += 1
                rnext += 1
            elif Map[bball[0]][bnext] == '.':
                mv_cnt += 1
                Map[bball[0]][bnext], Map[bball[0]][bball[1]] = Map[bball[0]][bball[1]], Map[bball[0]][bnext]
                bball[1] += 1
                bnext += 1
            if mv_cnt == 0:
                break
    rball = []
    bball = []
    for i in range(N):
        if 'R' in Map[i]:
            rball.append(i)
            rball.append(Map[i].index('R'))
        if 'B' in Map[i]:
            bball.append(i)
            bball.append(Map[i].index('B'))
    return 0, Map, rball[0], rball[1], bball[0], bball[1]


def bfs():
    q = deque()
    q.append((bord, 1))
    while q:
        formap, cnt = q.popleft()
        if cnt > 10:
            return -1
        for j in range(1, 5):
            M = copy.deepcopy(formap)
            tmp, maps, E, F, G, H = move(j, M)
            if tmp == 1:
                return cnt
            if (E, F, G, H) not in visit and tmp != -1:
                visit.append((E, F, G, H))
                inputmap = copy.deepcopy(maps)
                q.append((inputmap, cnt+1))

    return -1


if __name__ == '__main__':
    N, M = map(int, input().split(" "))
    bord = []
    for i in range(N):
        bord.append(list(input()))
    # 상하좌우1234
    answer = []
    visit = []

    for i in range(N):
        if 'R' in bord[i]:
            Rx, Ry = i, bord[i].index('R')
        if 'B' in bord[i]:
            Bx, By = i, bord[i].index('B')
    visit.append((Rx, Ry, Bx, By))
    print(bfs())

bamgoesn 1년 전 30

반례입니다.

7 5
#####
###.#
##.O#
#R..#
#####
###B#
#####

정답: 2
출력: -1

5 10
##########
#.#......#
##.......#
#OR..B.#.#
##########

정답: 7
출력: -1

4 7
#######
##R...#
#O.#.B#
#######

정답: 2
출력: 4

7 4
####
#B##
####
#.##
#R##
#O##
####

정답: 1
출력: -1

10 5
#####
#..##
#.O##
#...#
#.R##
##.##
##.##
#.###
#.B.#
#####

정답: 1
출력: 2

hhosu107 1년 전 0

감사합니다. early stopping을 잘못 적용하고 있었어요 (반례 중 2번째 항목)

dnpdhd 1년 전 0

감사합니다.. 저도 2번째 항목에서 break를 써야하는데 return을 쓰고 있었네요. 덕분에 해결하였습니다 감사합니다.

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

문제

문제

출처

ICPC

있는 TC 전부 넣었습니다. 8% 반례도와주세요 ㅠㅠ

ckd5508 1년 전 2

bamgoesn 1년 전 30

hhosu107 1년 전 0

dnpdhd 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말