14500-테트로미노

1x1인 정사각형을 여러개 이어서 붙인 도형(테트로미노)가 5가지 있음.

MXN 크기의 종이가 있다. 얘는 1x1크기로 나눠짐. 이 종이에 테트로미노를 1장 놓았을 때 그 종이에 써진 값의 합의 최대값 찾기.

전부다 해볼 수 있을까?

ㅁㅁㅁㅁ : row * (col-3)
ㅁ
ㅁ
ㅁ
ㅁ: (row-3) * col

ㅁㅁ
ㅁㅁ: (row-1)(col-1)
...

이런식으로 모든 케이스 구하면 (회전, 대칭 가능) 19가지 도형 모양이 있음.

근데 얘네들 모든 케이스 다 더해봐야 row*col이 안될거임.

row와 col은 최대 500까지 가짐.

500*500*19 = 4750000 500만 정도 되는데 이는 충분히 브루트 포스 할 수 있음.

int paper[500][500];
int block[19][3][2] = {
    {{0,1}, {0,2}, {0,3}},
    {{1,0}, {2,0}, {3,0}},
    {{1,0}, {1,1}, {1,2}},
    {{0,1}, {1,0}, {2,0}},
    {{0,1}, {0,2}, {1,2}},
    {{1,0}, {2,0}, {2,-1}},
    {{0,1}, {0,2}, {-1,2}},
    {{1,0}, {2,0}, {2,1}},
    {{0,1}, {0,2}, {1,0}},
    {{0,1}, {1,1}, {2,1}},
    {{0,1}, {1,0}, {1,1}},
    {{0,1}, {-1,1}, {-1,2}},
    {{1,0}, {1,1}, {2,1}},
    {{0,1}, {1,1}, {1,2}},
    {{1,0}, {1,-1}, {2,-1}},
    {{0,1}, {0,2}, {-1,1}},
    {{0,1}, {0,2}, {1,1}},
    {{1,0}, {2,0}, {1,1}},
    {{1,0}, {2,0}, {1,-1}},
};

int main(int argc, const char * argv[]) {

    int row, col;
    cin>>row>>col;
    int answer = 0;

    for(int i = 0; i<row; i++) {
        for(int j = 0; j<col; j++) {
            cin>>paper[i][j];
        }
    }

    for(int i = 0; i<19; i++) {
        for(int r = 0; r<row; r++) {

            for(int c=0; c<col; c++) {
                int sum = paper[r][c];
                bool isRange = true;
                for(int k=0; k<3; k++) {

                    int rVal = r + block[i][k][0];
                    int cVal = c + block[i][k][1];

                    if(rVal < 0 || rVal >= row || cVal < 0 || cVal >= col) {
                        isRange = false;
                        break;
                    }

                    sum += paper[rVal][cVal];
                }
                if(isRange) {
                    answer = max(answer, sum);
                }
            }
        }
    }

    cout<<answer<<endl;

    return 0;
}