완전 탐색을 이용한 구현 문제이다. 문제를 보면 총 5가지 종류의 테트로미노가 존재하는데 거기다가 회전과 대칭까지 존재한다. 구현 자체는 어렵지 않지만 굉장히 귀찮은 문제였다. 다른 분들이 푼 것을 보니 DFS
를 이용하여 문제를 푼 분들도 있던데 나는 간단히 반복문 노가다(?)를 통해 풀었다.
#include <iostream>
#include <algorithm>
using namespace std;
int N, M, res = 0, tmp;
int A[501][501];
void case1() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M - 3; j++) {
tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i][j + 3];
res = max(res, tmp);
}
}
for (int i = 0; i < N - 3; i++) {
for (int j = 0; j < M; j++) {
tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 3][j];
res = max(res, tmp);
}
}
}
void case2() {
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M - 1; j++) {
tmp = A[i][j] + A[i][j + 1] + A[i + 1][j] + A[i + 1][j + 1];
res = max(res, tmp);
}
}
}
void case3() {
for (int i = 0; i < N - 2; i++) {
for (int j = 0; j < M - 1; j++) {
tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 2][j + 1];
res = max(res, tmp);
tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i][j + 1];
res = max(res, tmp);
tmp = A[i][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 2][j + 1];
res = max(res, tmp);
tmp = A[i + 2][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 2][j + 1];
res = max(res, tmp);
}
}
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M - 2; j++) {
tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j];
res = max(res, tmp);
tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j + 2];
res = max(res, tmp);
tmp = A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 1][j + 2];
res = max(res, tmp);
tmp = A[i][j+2] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 1][j + 2];
res = max(res, tmp);
}
}
}
void case4() {
for (int i = 0; i < N - 2; i++) {
for (int j = 0; j < M - 1; j++) {
tmp = A[i][j] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 2][j + 1];
res = max(res, tmp);
tmp = A[i][j + 1] + A[i + 1][j + 1] + A[i + 1][j] + A[i + 2][j];
res = max(res, tmp);
}
}
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M - 2; j++) {
tmp = A[i + 1][j] + A[i + 1][j + 1] + A[i][j + 1] + A[i][j + 2];
res = max(res, tmp);
tmp = A[i][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 1][j + 2];
res = max(res, tmp);
}
}
}
void case5() {
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M - 2; j++) {
tmp = A[i][j] + A[i][j + 1] + A[i][j + 2] + A[i + 1][j + 1];
res = max(res, tmp);
tmp = A[i][j + 1] + A[i + 1][j] + A[i + 1][j + 1] + A[i + 1][j + 2];
res = max(res, tmp);
}
}
for (int i = 0; i < N - 2; i++) {
for (int j = 0; j < M - 1; j++) {
tmp = A[i][j] + A[i + 1][j] + A[i + 2][j] + A[i + 1][j + 1];
res = max(res, tmp);
tmp = A[i + 1][j] + A[i][j + 1] + A[i + 1][j + 1] + A[i + 2][j + 1];
res = max(res, tmp);
}
}
}
void solution() {
case1();
case2();
case3();
case4();
case5();
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> A[i][j];
}
}
solution();
return 0;
}