トロミノ

質問する

ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.

正方形は互いに重ならない.

図形はすべてつながっています.

正方形のエッジの間には接続されているはずです.つまり、必ずしも頂点と重なる必要はありません.

4つの正方形を結ぶポリオミノをトロミノといい、以下の5種類があります.

美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.

入力

第1行目は、用紙の長手方向サイズNおよび横方向サイズMを与える.(4 ≤ N, M ≤ 500)
2行目からN行の紙に数字が書いてあります.i 1行目のj個の数字は、上からiの1番目のセル、左からjの1番目のセルに書かれた数字である.入力は1000を超えない自然数を与えます.

しゅつりょく

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

ソリューション

接続

矩形の最大和は4であり,DFSにより4個の矩形の和を求める.

十字架から一方向一方向の形状(ピンクの形状)をDFSで実現するのは難しいと考えられています.
もう一つの関数を作って実現します.

n,m = map(int,input().split())

grid = list(list(map(int,input().split())) for _ in range(n))
max_val = max(map(max, grid))


dr = [0,1,0,-1]
dc = [1,0,-1,0]

def dfs(r,c,cnt,S) :
    global a 

    if a >= S + max_val * (4-cnt) :
        return 
    if cnt >=4 :
        if S>a :
            a = S
        return
    
    for d in range(4) :
        nr = r + dr[d]
        nc = c + dc[d]

        if 0<=nr<n and 0<=nc<m and not visited[nr][nc] :
            visited[nr][nc] = 1
            dfs(nr,nc,cnt+1,S+grid[nr][nc])
            visited[nr][nc] = 0 

def cross(r,c,S) :
    global a 
    tmp = []
    for d in range(4) :
        nr = r + dr[d]
        nc = c + dc[d]
        if 0<=nr<n and 0<=nc<m :
            S += grid[nr][nc]
            tmp.append(grid[nr][nc])
    if len(tmp) == 3 :
        if S > a :
            a = S
    if len(tmp) == 4 : 
        for t in tmp :
            if S - t >a :
                a = S  - t

a = 0
visited = [[0]*m for _ in range(n)]
for r in range(n) :
    for c in range(m) :
        visited[r][c] = 1 
        dfs(r,c,1,grid[r][c])
        visited[r][c] = 0
        cross(r,c,grid[r][c])

print(a)