시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 539 226 176 49.718%

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

  • 정사각형은 서로 겹치면 안된다.
  • 도형은 모두 연결되어 있어야 한다.
  • 정사각형의 꼭지점끼리 연결되어 있어야 한다. 즉, 변과 꼭지점이 맞닿아있으면 안된다.

정사각형 4개를 이어 븥인 도형은 테트로미노라고 하며, 다음과 같은 5가지가 있다.

오늘 아름이는 크기가 N×M인 종이 위에 폴리오미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 써 있다.

폴리오미노 하나를 적절히 놓아서 놓인 칸에 써있는 수의 합을 최대로 하는 프로그램을 작성하시오.

폴리오미노의 한 정사각형은 하나의 칸만을 정확하게 포함해 네 개의 칸을 포함해야 하며, 회전, 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 써 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 써 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 폴리오미노가 놓인 칸에 써인 수의 합의 최대값을 출력한다.

예제 입력

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

예제 출력

19

예제 입력 2

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

예제 출력 2

20

예제 입력 3

4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1

예제 출력 3

7

힌트

출처

  • 문제를 만든 사람: baekjoon
  • 데이터를 추가한 사람: stack