글 읽기 - 반례가 있을까요? 42%

whiteleo100 1년 전 0

1. 코인 2개다 범위 내인 경우

-> 방문 여부 확인

-> 양쪽 다 벽인지 확인

-> 벽이 있는 경우 고려해서 이동

2. 둘 다 범위가 아닌 경우

3. 하나만 범위가 아닌 경우

-> 정답! 출력

이런식의 알고리즘인데.. 반례가 뭐가 있을까요?

import sys,collections
row, col = map(int, sys.stdin.readline().split())
matrix = [list(sys.stdin.readline().rstrip()) for _ in range(row)]
visited1 = [[False for _ in range(col)] for _ in range(row)]
visited2 = [[False for _ in range(col)] for _ in range(row)]
coin = []
for i in range(row):
    for j in range(col):
        if matrix[i][j] == 'o':
            coin.extend([i,j])
visited1[coin[0]][coin[1]] = True
visited2[coin[2]][coin[3]] = True
coin = collections.deque([coin])
cnt = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
while coin and cnt < 10:
    cnt += 1
    for _ in range(len(coin)):
        c = coin.pop()
        for i in range(4):
            x1 ,y1 = dx[i] + c[0],dy[i] + c[1]
            x2, y2 = dx[i] + c[2], dy[i] + c[3]
            if 0<= x1 < row and 0<= y1 < col and 0<= x2 < row and 0<= y2 < col: # 둘 다 범위 내임
                if visited1[x1][y1] and visited2[x2][y2]: # 이미 방문함
                    continue
                if matrix[x1][y1] == '#' and matrix[x2][y2] == '#': # 양쪽 다 벽
                    continue
                elif matrix[x1][y1] == '#': # x2, y2 만 움직임
                    coin.appendleft([c[0],c[1],x2,y2])
                    visited2[x2][y2] = True
                elif matrix[x2][y2] == '#': # x1,y1만 움직임
                    coin.appendleft([x1,y1,c[2],c[3]])
                    visited1[x1][y1] = True
                else: # 벽이 없음
                    coin.appendleft([x1,y1,x2,y2])
                    visited1[x1][y1] = True
                    visited2[x2][y2] = True
            elif  (not(0<= x1 < row) or not(0<= y1 < col)) and (not(0<= x2 < row) or not(0<= y2 < col)):  # 두개 다 범위가 아닌 경우
                continue
            else: # 둘 중 하나만 범위 내임
                print(cnt)
                exit()
print(-1)

skfro2013 1년 전 1

10번 보다 많이 누르면, -1입니다. 10번까지 포함.

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

문제

문제

출처

ICPC

반례가 있을까요? 42%

whiteleo100 1년 전 0

skfro2013 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말