白駿/トロミノ/14500

Question
質問リンク
Gold 5
ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.
正方形は互いに重なり合ってはいけない.
図形はすべてつながっていなければなりません.
正方形の辺はつながっていなければならない.つまり、必ずしも頂点と重なる必要はありません.
4つの正方形を結ぶポリオミノをトロミノといい、以下の5種類があります.

美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.
Input
第1行目は、用紙の長手方向サイズNおよび横方向サイズMを与える.(4 ≤ N, M ≤ 500)
2行目からN行の紙に数字が書いてあります.i 1行目のj個の数字は、上からiの1番目のセル、左からjの1番目のセルに書かれた数字である.入力は1000を超えない自然数を与えます.

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

Output
最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.

19

Logic
基本構造きほんこうぞう:brute brute
仮に、N×N配列において、ある「一マス」を基準としてテトロミノパターンを描き、左上からすべての場合の数字を順次描き、最大値を求める.
これには,標準となるセルから描くのではなく,標準となるセルを起点としてnxnセル内に描く方法が含まれる.(「ㅘ」など、左上隅の標準格ではなく、描画方法)
絵をもう一度見てください.

上記の5つのグラフィックを1つの「1つのグリッド」に基づいて描画すると、
スカイブルー:2種類
黄色:1種
オレンジ:4種
グリーン:4種類
ピンク:4種
全部で15種類あります.
以上の15種は,NX Nの配列の中で右下から描き始め,残りの行や列から15種を描けるか否かを判断する.
Code

from sys import stdin

r,c = map(int,stdin.readline().split())

data=[]
for _ in range(r):
    buff = list(map(int,stdin.readline().split()))
    data.append(buff)

sums=0
for ir in range(r):
    for ic in range(c):
        # ㅣ
        if ir+3 < r : sums=max(sums,data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir+3][ic])
        # ㅡ
        if ic+3 < c : sums=max(sums,sum(data[ir][ic:ic+4]))
        if ir+2 < r and ic+1 < c :
            sums = max(sums,data[ir][ic+1] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+2][ic+1], data[ir][ic+1] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+2][ic], data[ir][ic+1] +data[ir+1][ic+1] +data[ir+2][ic]+data[ir+2][ic+1])
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir][ic+1])
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+2][ic+1], data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir+1][ic+1])
            sums = max(sums,data[ir][ic] +data[ir][ic+1] +data[ir+1][ic+1]+data[ir+2][ic+1], data[ir][ic] +data[ir+1][ic] +data[ir+2][ic]+data[ir+2][ic+1])
        if ir+1 < r and ic+2 < c :
            sums = max(sums,data[ir][ic+1] +sum(data[ir+1][ic:ic+3]), data[ir][ic+1] +data[ir][ic+2] +data[ir+1][ic]+data[ir+1][ic+1], data[ir][ic+2] +sum(data[ir+1][ic:ic+3]))
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir][ic+1]+data[ir][ic+2])
            sums = max(sums,data[ir][ic] +data[ir][ic+1] +data[ir+1][ic+1]+data[ir+1][ic+2], data[ir][ic] +data[ir][ic+1] +data[ir][ic+2]+data[ir+1][ic+1])
            sums = max(sums,data[ir][ic] +data[ir][ic+1] +data[ir][ic+2]+data[ir+1][ic+2], data[ir][ic] +data[ir+1][ic] +data[ir+1][ic+1]+data[ir+1][ic+2])
        # ㅁ
        if ir+1 < r and ic+1 < c :
            sums = max(sums,data[ir][ic] +data[ir+1][ic] +data[ir][ic+1]+data[ir+1][ic+1])

print(sums)