from collections import deque dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] def pull(target, another, dir): movex, movey = target[0],target[1] if (dir == 0): for y in range(target[1]-1, -1, -1): if (grid[y][target[0]] != '#' and not (another[0] == target[0] and another[1] == y)): movey = y else: break elif (dir == 1): for x in range(target[0]+1, X, +1): if (grid[target[1]][x] != '#' and not (another[0] == x and another[1] == target[1])): movex = x else: break elif (dir == 2): for y in range(target[1]+1, Y, +1): if (grid[y][target[0]] != '#' and not (another[0] == target[0] and another[1] == y)): movey = y else: break else: for x in range(target[0]-1, -1, -1): if (grid[target[1]][x] != '#' and not (another[0] == x and another[1] == target[1])): movex = x else: break return [movex, movey] def pullRedandBlue(dir, red, blue): if ((dir == 0 and blue[1] < red[1]) or (dir == 1 and blue[0] > red[0]) or (dir == 2 and blue[1] > red[1]) or (dir == 3 and blue[0] < red[0])): # y값 작은 구슬 먼저 이동 blue = pull(blue, red, dir) red = pull(red, blue, dir) else: red = pull(red, blue, dir) blue = pull(blue, red, dir) return red, blue def checkPassHole(dir, cur, next): if (dir == 0): if (next[0] == exit[0] and next[1] <= exit[1] <= cur[1]): return True elif (dir == 1): if (next[1] == exit[1] and cur[0] <= exit[0] <= next[0]): return True elif (dir == 2): if (next[0] == exit[0] and cur[1] <= exit[1] <= next[1]): return True else: if (next[1] == exit[1] and next[0] <= exit[0] <= cur[0]): return True return False def BFS(start): queue = deque() queue.append([start, 1]) visited = [] visited.append(start) while (queue): cur, curCnt = queue.popleft() if (curCnt > 10): return -1 curRed, curBlue = cur[0], cur[1] for i in range(4): nextRed, nextBlue = pullRedandBlue(i, curRed, curBlue) if ([nextRed, nextBlue] in visited): continue # 파란 위치가 구멍 if (checkPassHole(i, curBlue, nextBlue)): continue # 빨간 위치가 구멍 if (checkPassHole(i, curRed, nextRed)): # 뒤따라 파란 공도 구멍으로 나오는 경우 if (nextBlue[0]+dx[i] == exit[0] and nextBlue[1]+dy[i] == exit[1]): continue else: return curCnt queue.append([[nextRed, nextBlue], curCnt + 1]) visited.append([nextRed, nextBlue]) return -1 Y, X = map(int, input().split()) grid = [list(input()) for _ in range(Y)] exit, red, blue = [-1, -1], [-1, -1], [-1, -1] for y in range(Y): for x in range(X): if (grid[y][x] == 'O'): exit[0], exit[1] = x, y elif (grid[y][x] == 'R'): red[0], red[1] = x, y grid[y][x] = '.' elif (grid[y][x] == 'B'): blue[0], blue[1] = x, y grid[y][x] = '.' print(BFS([red, blue]))

제출 #56227

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: