BOJ 14500 - 테트로미노

문제

https://www.acmicpc.net/problem/14500

 

 

풀이

완전탐색으로 문제를 해결할 수 있다

5가지 도형을 회전해서 얻을 수 있는 모든 도형을 종이 위에 올리면서 최대값을 구한다

최대 시간은 500 * 500 * 19 * 4 = 19000000 이므로완전탐색으로 해결 가능하다

 

코드

python

figures = [
    [[0, 0], [0, 1], [1, 0], [1, 1]],
    [[0, 0], [0, 1], [0, 2], [0, 3]],
    [[0, 0], [1, 0], [2, 0], [3, 0]],
    [[0, 0], [0, 1], [0, 2], [-1, 2]],
    [[0, 0], [1, 0], [2, 0], [2, 1]],
    [[0, 0], [1, 0], [0, 1], [0, 2]],
    [[0, 0], [0, 1], [1, 1], [2, 1]],
    [[0, 0], [0, 1], [-1, 1], [-1, 2]],
    [[0, 0], [1, 0], [1, 1], [2, 1]],
    [[0, 0], [0, 1], [-1, 1], [0, 2]],
    [[0, 0], [1, 0], [2, 0], [1, 1]],
    [[0, 0], [0, 1], [0, 2], [1, 1]],
    [[0, 0], [1, 0], [2, 0], [1, -1]],
    [[0, 0], [0, 1], [1, 1], [1, 2]],
    [[0, 0], [1, 0], [1, -1], [2, -1]],
    [[0, 0], [1, 0], [1, 1], [1, 2]],
    [[0, 0], [0, 1], [1, 0], [2, 0]],
    [[0, 0], [0, 1], [0, 2], [1, 2]],
    [[0, 0], [1, 0], [2, 0], [2, -1]],
]
 
paper = [[0 for _ in range(505)] for _ in range(505)]
answer = 0
 
n, m = map(int, input().split())
 
for i in range(1, n + 1):
    r = list(map(int, input().split()))
    for j in range(1, m + 1):
        paper[i][j] = r[j - 1]
 
 
for i in range(1, 501):
    for j in range(1, 501):
        for k in range(19):
            sum = 0
            for l in range(4):
                y = i + figures[k][l][0]
                x = j + figures[k][l][1]
 
                if paper[y][x] == 0:
                    sum = 0
                    break
 
                sum += paper[y][x]
 
            answer = max(answer, sum)
 
 
print(answer)