글 읽기 - 36퍼에서 계속 막힙니다... 반례 찾아주실분 계신가요ㅠㅠ

jwb2906 3년 전 0

36퍼에서 넘어가지를 못하네요....

반례좀 부탁드립니다.....

import sys
from collections import deque

def main():
    sys.stdin = open("input.txt", "r")
    n,m = map(int, input().split())
    board = []
    max_value = max(n,m)
    answer = 0
    for i in range(n):
        line = input()
        arr = []
        for j in line:
            arr.append(j)
        board.append(arr)

    #for i in board:
    #    print(i)
    check = 0
    p_r = []
    p_b = []
    p_end = []
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'B':
                p_b.append([0, i, j, 10])
            elif board[i][j] == 'R':
                p_r.append([0, i, j, 10])
            elif board[i][j] == "O":
                p_end.append([i,j])


    q = deque()
    q.append([p_r[0], p_b[0]])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while(q):
        #print(q)
        buf = q.popleft()
        num = buf[0][0]
        p_r = [buf[0][1], buf[0][2]]
        p_b = [buf[1][1], buf[1][2]]
        direction = buf[0][3]
        re_direction = direction +2
        if re_direction > 3:
            re_direction -= 4
        if p_r == p_end[0] and p_b != p_end[0]:
            answer = num
            return answer

        if num  == 10 :
            continue

        else:
            for i in range(4):
                rx = p_r[0]
                ry = p_r[1]
                bx = p_b[0]
                by = p_b[1]
                if i == re_direction:
                    continue
                r_count = 0
                b_count = 0
                while(1):
                    rxx = rx + dx[i]
                    ryy = ry + dy[i]
                    bxx = bx + dx[i]
                    byy = by + dy[i]
                    if board[rxx][ryy] == "#" and board[bxx][byy] == "#":
                        break
                    else:
                        if board[rxx][ryy] != "#" and board[rx][ry] != "O":
                            rx = rxx
                            ry = ryy
                            r_count += 1
                        if board[bxx][byy] != "#" and board[bx][by] != "O":
                            bx = bxx
                            by = byy
                            b_count += 1
                        if board[rx][ry] == "O" and board[bx][by] == "O":
                            check = 1
                            break
                        elif board[rx][ry] == "O" and board[bxx][byy] == "#":
                            return num+1
                        elif board[rxx][ryy] == "#" and board[bx][by] == "O":
                            break
                if board[rx][ry] != "O" and board[bx][by] =="O":
                    continue
                if board[rx][ry] == "O" and board[bx][by] == "O":
                    continue
                if [rx, ry] == [bx, by]:
                    if r_count > b_count:
                        rx = rx - dx[i]
                        ry = ry - dy[i]
                    elif r_count < b_count:
                        bx = bx - dx[i]
                        by = by - dy[i]
                if [rx, ry] != p_r or [bx, by] != p_b:
                    q.append([[num+1, rx, ry, i], [num+1, bx, by, i]])
    if check == 1:
        return -1
    if len(q) == 0:
        return -1


re = main()
print(re)

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

문제

문제

출처

ICPC

36퍼에서 계속 막힙니다... 반례 찾아주실분 계신가요ㅠㅠ

jwb2906 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말