글 읽기 - gaaaaaaaaaarden 반례요청

alftjd1 4년 전 0

코드가 개선해야 할 점이 많고 느린 것이 사실이지만 70%~ 쯔음에 '틀렸습니다.' 가 발생하는 것에 미련이 남아

반례 제공을 부탁드리는 것을 요청합니다.

from itertools import combinations
from copy import deepcopy
from sys import stdin

input = stdin.readline

n, m, G, R = map(int, input().split())
world = [[0] * (m + 2)] + \
        [[0] + list(map(int, input().split())) + [0] for _ in range(n)] + \
        [[0] * (m + 2)] # 시간 효율을 증가 시키기 위해(27,35줄에 if문 하나를 줄이기 위해)
                        # 테두리를 0으로 감쌈

temp = [(i, j) for i in range(1, n + 1) for j in range(1, m + 1) if world[i][j] == 2]
# 배양액을 놓을 수 있는 위치를 temp에 추가

report = []
for p_temp in combinations(temp, G + R): # 초록, 빨강 배양액을 놓을 수 있는 경우(중복 x)
    for R_temp in combinations(p_temp, R): # 빨강 배약액을 놓을 수 있는 경우 

        G_temp = tuple(set(p_temp).difference(set(R_temp)))# R_temp와 중복 x
        re = 0                                             # R_temp = 빨강 배양액
                                                           # B_temp = 초록 배양액
        graph = deepcopy(world)                            # 맵에 표시할 것이므로 원본 보존
        while G_temp and R_temp:                           # 둘중 하나가 고갈 되면 더이상 꽃이 필수 없음

            g_temp = list(G_temp[:])                       # 턴표시를 하기 위한 구분
            G_temp = []                                    # 즉 원래 있던 것을 복사하고, 
            while g_temp:                                  # 중복을 허용하지 않게 하기 위해 원본값을 제거 
                i, j = g_temp.pop()                        # 방문한 곳은 다시 제거한 원본값에 추가
                for x, y in [1, 0], [0, 1], [-1, 0], [0, -1]:
                    if graph[i + x][j + y]:
                        G_temp.append((i + x, j + y))

            r_temp = list(R_temp[:])
            R_temp = []
            while r_temp:
                i, j = r_temp.pop()
                for x, y in [1, 0], [0, 1], [-1, 0], [0, -1]:
                    if graph[i + x][j + y]:
                        R_temp.append((i + x, j + y))

            for x, y in G_temp + R_temp:                    # 방문 처리 
                graph[x][y] = 0

            a_temp = set(G_temp).intersection(set(R_temp))  # 집합자료형으로 30, 38줄에서 추가한 값중 동시에 방문한 곳은 
            G_temp = list(set(G_temp).difference(a_temp))   # a_temp 에 저장(길이로 꽃이 생성됨을 카운트)
            R_temp = list(set(R_temp).difference(a_temp))   # 서로 겹친 곳은 배양액이 있으면 안되므로 제거(44,45줄)
            re += len(a_temp)                               # 생성된 꽃 개수 추가

        report.append(re) # 탐색이 끝나면 각각 끝나는 것마다 report에 추가

print(max(report))        # 모든 경우를 탐색후 그 중 가장 큰 값을 출력 

paa0609 4년 전 3

반례입니다.

입력

3 3 1 2

0 0 0

2 2 0

0 2 0

정답 : 0

출력 : 1

alftjd1 4년 전 0

아주 휼륭한 반례였습니다.

감사합니다.

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

문제

문제

출처

ICPC

gaaaaaaaaaarden 반례요청

alftjd1 4년 전 0

paa0609 4년 전 3

alftjd1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말