글 읽기 - 92%에서 틀리는데 반례를 못찾겠습니다.

qkrwnstns52 2년 전 0

반례가 있을까요... ㅠㅠ

from collections import deque
import sys

input = sys.stdin.readline

board = []
for _ in range(8):
    board.append(list(map(str, input())))
visited = [[0] * 8 for _ in range(8)]

dx = [0, -1, -1, -1, 0, 1, 1, 1, 0]
dy = [0, -1, 0, 1, 1, 1, 0, -1, -1]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    while q:
        walls = []
        tmp = []
        for i in range(8):
            for j in range(8):
                if board[i][j] == '#':
                    walls.append((i, j))
        x, y = q.popleft()
        if x == 0 and y == 7:
            return 1
        for i in range(9):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < 8 and -1 < ny < 8:
                if board[nx][ny] == '.' and visited[nx][ny] == 0:
                    tmp.append((nx, ny))
        for r in range(8):
            for c in range(8):
                if board[r][c] == '#':
                    walls.append((r, c))
        walls.sort(key=lambda x:(-x[0], -x[1]))
        for wall in walls:
            board[wall[0]][wall[1]] = '.'
            nr = wall[0] + 1
            nc = wall[1]
            if nr == 8:
                continue
            board[nr][nc] = '#'
        for pos in tmp:
            if board[pos[0]][pos[1]] != '#':
                visited[pos[0]][pos[1]] = 1
                q.append((pos[0], pos[1]))
    return 0

print(bfs(7, 0))

djj 2년 전 0

혹시.. 찾으셨나요...ㅠㅠ 저도 92%에서 자꾸 오류나는데...

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

문제

문제

출처

ICPC

92%에서 틀리는데 반례를 못찾겠습니다.

qkrwnstns52 2년 전 0

djj 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말