[백준] 14500번 테트로미노 파이썬

폴리오미노 : 1x1 크기 정사각형 여러 개 이어 붙인 도형

- 정사각형은 서로 겹치면 안 됨.

- 도형은 모두 연결되어야 함.

- 정사각형의 변끼리 연결되어 있어야 함. (꼭짓점끼리만 맞닿아 있으면 안 됨.)

4개를 이어 붙이면 "테트로미노" -> 5가지

NxM 크기 종이 위에 테트로미노 하나 놓을 때, 종이 1x1 크기의 칸 하나에는 정수가 쓰여져 있음.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성해라.

테트로미노는 반드시 한 정사각형이 한 칸을 포함하도록 놓고, 회전이나 대칭 가능.

 

- 입력

1줄 : 종이의 세로 크기 N, 가로 크기 M

2~N줄 : 종이에 쓰여 있는 수. ( i번째 줄의 j번째 수)

 

- 출력

테트로미노가 놓인 칸에 쓰인 수들의 합 최댓값

 

 

14500번 테트로미노

 

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

14500번: 테트로미노