글 읽기 - 게시판의 모든 예외 케이스를 통과하는데 틀리네요 도와주세요 .. ㅠ

galid1 3년 전 0

게시판의 모든 예외 케이스가 통과됩니다...

생각한 예외 경우

1. "." 이 아닌, "열 수 있는 문", "$, 열쇠"를 획득한 경우도 탐색을 위해 q에 삽입

2. 열쇠가 없이 방문 했던 문들의 경우 열쇠를 획득한 경우 다시 탐색(이 때 해당 문을 찾아갈 수 없는 경우에는 방문을 하지 않음)

테스트 해본 케이스들

# 1
# 5 5
# ABABA
# AabaB
# Bb$aB
# AbabB
# AABAa
# 0

# 3
# 5 17
# *****************
# .............**$*
# *B*A*P*C**X*Y*.X.
# *y*x*a*p**$*$**$*
# *****************
# cz
# 5 11
# *.*********
# *...*...*x*
# *X*.*.*.*.*
# *$*...*...*
# ***********
# 0
# 7 7
# *ABCDE*
# X.....F
# W.$.G
# V.$.H
# U.$.J
# T.....K
# *SQPMI*
# irony

# 1
# 6 3
# ***
# ...
# *X*
# *X*
# *$*
# ***
# x

# 1
# 2 2
# $
# $
# 0

# 1
# 3 3
# aaa
# a$a
# aaa
# 0

# 4 5
# 1
# *A***
# *$*a.
# **$**
# **A**
# 0
#
# 1
# 5 11
# *x*********
# *...*...*.*
# *X*.*.*.*.*
# *$*...*...*
# ***********
# 0

# 1
# 3 4
# ****
# *$A*
# ****
# a

import sys
from collections import deque


def solve():
    global n, m, keys, dx, dy, board

    q = deque()
    # 진입 지점 찾기
    find_entries(q)
    
    while q:
        cx, cy = q.popleft()

        for d in range(4):
            nx, ny = cx + dx[d], cy + dy[d]
            if is_valid(nx, ny):
                handle_point(q, nx, ny)

                
def find_entries(q):
    global n, m, visited

    # 맨위, 맨아래
    for i in (0, n - 1):
        for j in range(m):
            if is_valid(j, i):
                handle_point(q, i, j)

    # 맨왼쪽, 맨 오른쪽
    for i in (0, m - 1):
        for j in range(n):
            if is_valid(j, i):
                handle_point(q, j, i)

                
def is_valid(x, y):
    global board, n, m, visited
    return 0 <= x < n and 0 <= y < m and not visited[x][y]


def handle_point(q, x, y):
    global board, docs, visited

    target = board[x][y]

    if target == '*':
        visited[x][y] = True
        return
    elif target == '.':
        q.append((x, y))
        visited[x][y] = True
    elif target == '$':
        q.append((x, y))
        docs.append('$')
        visited[x][y] = True
    elif target.isalpha():
        # 문
        if target.isupper():
            if can_open(target):
                q.append((x, y))
                visited[x][y] = True
            else:
                save_door(target, x, y)
        # 열쇠
        else:
            q.append((x, y))
            keep_key_and_open(q, target)
            visited[x][y] = True


def save_door(door, x, y):
    global doors, visited
    if not visited[x][y]:
        doors[door].append([x, y])


def keep_key_and_open(q, key):
    global keys, doors, visited
    keys[key.upper()] = True

    # 키를 찾았으니 이전에 방문해서 열지 못한 문들을 다시 열어서 q에 넣음
    for door_x, door_y in doors[key.upper()]:
        if not visited[door_x][door_y]:
            q.append((door_x, door_y))
            visited[door_x][door_y] = True


def can_open(door):
    global keys
    return keys[door]


# 입력
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    board = []
    for i in range(n):
        board.append(list(sys.stdin.readline().strip()))

    # 열쇠와, 문 초기화
    keys = {chr(i): False for i in range(65, 91)}
    doors = {chr(i): [] for i in range(65, 91)}
    for k in list(sys.stdin.readline().strip()):
        keys[k.upper()] = True

    # 방문 배열
    visited = [[False for _ in range(m)] for _ in range(n)]

    # 방향
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)

    # 정답 문서 배열
    docs = []
    solve()
    print(len(docs))

exponential_e 3년 전 1

아래 데이터에서 잘못된 답을 출력하고 있습니다.

입력
1
5 11
*.*********
*.*.*....x*
*X*.*.*.*.*
*$....*.*.*
*********.*
0

출력
0
답
1

galid1 3년 전 1

감사합니다 ..

출입구를 찾는 코드에서, 맨위 맨아래를 찾는 부분의 i, j 가 뒤집혀 있었네요

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

문제

문제

출처

ICPC

게시판의 모든 예외 케이스를 통과하는데 틀리네요 도와주세요 .. ㅠ

galid1 3년 전 0

exponential_e 3년 전 1

galid1 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말