Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

(C[:-1][:,:] == C[1:][:,r][])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
R = np.arange(1,H+1)[None,:]
L = np.arange(1,H+1)[:,None]
for r in range(H):
    for l in range(H):
        dp_1[:,r-l+H,r+l+2] = (C[:-1][:,l] == C[1:][:,r])
np.cumsum(dp_1,out=dp_1,axis=2)

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[:,R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = (C[:-1][:,:,None] == C[1:][:,None,:])
np.cumsum(dp_1,out=dp_1,axis=2)

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

equal = np.empty((W-1,H,H),dtype=np.bool)
for n in range(W-1):
    equal[n,:,:] = (C[n][:,None] == C[n+1][None,:])
dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[:,R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
np.cumsum(dp_1,out=dp_1,axis=2)

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

equal = np.empty((H,H,W-1),dtype=np.bool)
for n in range(W-1):
    equal[:,:,n] = (C[n][:,None] == C[n+1][None,:])
dp_1 = np.zeros((H+H+1,H+H+1,W-1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None],:] = equal
np.cumsum(dp_1,out=dp_1,axis=1)

INF = 10**18
# R-L+H -> min cost
dp = np.full((H+H+1,W-1),INF,dtype=np.int64)
dp[H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((H+H+1,W-1),INF,dtype=np.int64)
    dp[1:,:] = np.minimum(dp[1:,:],prev[:-1,:])
    dp[:-1,:] = np.minimum(dp[:-1,:],prev[1:,:])
    dp += dp_1[:,n,:]

answer = dp[H].sum()
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

equal = np.empty((H,H,W-1),dtype=np.bool)
for n in range(W-1):
    equal[:,:,n] = (C[:,n][:,None] == C[:,n+1][None,:])
dp_1 = np.zeros((H+H+1,H+H+1,W-1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None],:] = equal
np.cumsum(dp_1,out=dp_1,axis=1)

INF = 10**18
# R-L+H -> min cost
dp = np.full((H+H+1,W-1),INF,dtype=np.int64)
dp[H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((H+H+1,W-1),INF,dtype=np.int64)
    dp[1:,:] = np.minimum(dp[1:,:],prev[:-1,:])
    dp[:-1,:] = np.minimum(dp[:-1,:],prev[1:,:])
    dp += dp_1[:,n,:]

answer = dp[H].sum()
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    equal = (col1[:,None] == col2[None,:])
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    L = np.arange(H+1)
    R = np.arange(H+1)
    dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
    np.cumsum(dp_1,out=dp_1,axis=1)
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    # まず、その瞬間のスコアを求める
    # L+R,R-L+H
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    for n in range(H+H+1):
        # R-L+H=n
        if n <= H:
            R0,L0 = 1,H-n+1
            R1,L1 = n,H
        else:
            L0,R0 = 1,n-H+1
            L1,R1 = H+H-n,H
        dp_1[n][L0+R0:L1+R1+2:2] = (col1[L0:L1+1] == col2[R0:R1+1])
    np.cumsum(dp_1,out=dp_1,axis=1)
#    for L in range(H+1):
#        for R in range(H+1):
#            x = col1[:L+1]
#            y = col2[:R+1]
#            n = min(L,R)
#            xr = x[::-1][:n+1]
#            yr = y[::-1][:n+1]
#            print(L,R,(xr==yr).sum(),dp_1[R-L+H,L+R])"""
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)



Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    # まず、その瞬間のスコアを求める
    # L+R,R-L+H
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    for n in range(H+H+1):
        # R-L+H=n
        if n <= H:
            R0,L0 = 1,H-n+1
            R1,L1 = n,H
        else:
            L0,R0 = 1,n-H+1
            L1,R1 = H+H-n,H
        dp_1[n][L0+R0:L1+R1+2:2] = (col1[L0:L1+1] == col2[R0:R1+1])
        np.cumsum(dp_1[n],out=dp_1[n])
    
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)