글 읽기 - 6087 문제 반례를 얻고 싶습니다.

ssango 4년 전 0

안녕하세요.

6087번을 풀면서 bfs랑 3차원 배열을 이용해서 문제를 풀어보았는데요.

반례를 얻고 싶어 질문 드렸습니다.

from collections import deque
m,n = map(int,input().split(' '))

q = deque()
matrix = []
dist= [[[-1]*4 for i in range(m)] for _ in range(n)]
ex,ey =0,0
for i in range(n):
    temp = list(input())
    if 'C' in temp:
        y=temp.index('C')
        if not q:
            for j in range(4):
                q.append((i,y,j))
                dist[i][y][j]=0
        else:
            ex,ey =i,y
    matrix.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs():
    while q:
        x,y,z=q.popleft()
        nx,ny = x+dx[z],y+dy[z]
        if x==ex and y==ey:
            print(dist[x][y][z])
            return
        #거울을 만들지 않고 그냥 진행
        if 0 <= nx <n  and 0 <= ny < m and dist[nx][ny][z] == -1 and matrix[nx][ny] !='*' :
            q.append((nx,ny,z))
            dist[nx][ny][z] = dist[x][y][z]
        #거울을 만들어 주어 비용을 추가해준다
        k =2 if z<2 else 0
        for i in range(k,k+2):
            if dist[x][y][i] == -1:
                q.append((x,y,i))
                dist[x][y][i] = dist[x][y][z]+1
bfs()

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

문제

문제

출처

ICPC

6087 문제 반례를 얻고 싶습니다.

ssango 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말