Problem:


Score : 800 points

Problem Statement

Mr. Takahashi has in his room an art object with H rows and W columns, made up of H \times W blocks.
Each block has a color represented by a lowercase English letter (a-z).
The color of the block at the i-th row and j-th column is c_{i,j}.  

Mr. Takahashi would like to dismantle the object, finding it a bit kitschy for his tastes.
The dismantling is processed by repeating the following operation:  

Choose one of the W columns and push down that column one row.
The block at the bottom of that column disappears.

Each time the operation is performed, a cost is incurred.
Since blocks of the same color have a property to draw each other together, the cost of the operation is the number of the pairs of blocks (p, q) such that:

The block p is in the selected column.

The two blocks p and q are horizontally adjacent (before pushing down the column).

The two blocks p and q have the same color.

Mr. Takahashi dismantles the object by repeating the operation H \times W times to get rid of all the blocks.
Compute the minimum total cost to dismantle the object.

Constraints

1 ≤ H ≤ 300

2 ≤ W ≤ 300

All characters c_{i,j} are lowercase English letters (a-z).

Partial Score

In test cases worth 300 points, W = 3.

Input

The input is given from Standard Input in the following format:

H W
c_{1,1}c_{1,2}..c_{1,W}
c_{2,1}c_{2,2}..c_{2,W}
:
c_{H,1}c_{H,2}..c_{H,W}

Output

Print the minimum total cost to dismantle the object.

Sample Input 1

2 3
rrr
brg

Sample Output 1

2

For example, the total cost of 2 can be achieved by performing the operation as follows and this is the minimum value.

Sample Input 2

6 3
xya
xya
ayz
ayz
xaz
xaz

Sample Output 2

0

The total cost of 0 can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column.

Sample Input 3

4 2
ay
xa
xy
ay

Sample Output 3

0

The total cost of 0 can be achieved by the following operations:

pushing down the right column one row;

pushing down the left column one row;

pushing down all of the right column;

and pushing down all of the left column.

Sample Input 4

5 5
aaaaa
abbba
ababa
abbba
aaaaa

Sample Output 4

24

Sample Input 5

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx

Sample Output 5

130



Sample input:
2 3
rrr
brg


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [[] for i in range(H + 1)]
C[0] = [0] * (W + 1)
for i in range(1, H + 1):
    C[i] = [0] + list(input())

ans = 0
INF = float('inf')
for i in range(1, W):
    dp = [[INF] * 330 for i in range(330)]
    g = [[0] * 330 for i in range(330)]

    for j in range(1, H + 1):
        for k in range(1, H + 1):
            g[j][k] = g[j - 1][k - 1]
            if C[j][i] == C[k][i + 1]:
                g[j][k] += 1

    dp[H][H] = 0
    for j in range(H, -1, -1):
        for k in range(H, -1, -1):
            if j > 0:
                dp[j - 1][k] = min(dp[j - 1][k], dp[j][k] + g[j][k])
            if k > 0:
                dp[j][k - 1] = min(dp[j][k - 1], dp[j][k] + g[j][k])

    ans += dp[0][0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
H, W = inpl()
C = [input() for _ in range(H)]

def calc_cost(L, R):
    global C
    P = [[0]*(H+1) for _ in range(2*H + 1)]
    for l in range(H):
        for r in range(H):
            P[l-r+H][min(l, r)] = int(C[l][L] == C[r][R])

    S = [[0]*(H+1) for _ in range(2*H + 1)]
    for i in range(1, 2*H + 1):
        r = H - abs(H-i)
        for j in range(r):
            S[i][j+1] = S[i][j] + P[i][j]

    DP = [[100000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = S[x-2*y+H][H-max(x-y, y)]
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(i, i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b
def max(a, b): return a if a > b else b
H, W = inpl()
C = [input() for _ in range(H)]

def calc_cost(L, R):
    global C
    P = [[0]*(H+1) for _ in range(2*H + 1)]
    for l in range(H):
        for r in range(H):
            P[l-r+H][min(l, r)] = int(C[l][L] == C[r][R])

    S = [[0]*(H+1) for _ in range(2*H + 1)]
    for i in range(1, 2*H + 1):
        r = H - abs(H-i)
        for j in range(r):
            S[i][j+1] = S[i][j] + P[i][j]

    DP = [[100000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = S[x-2*y+H][H-max(x-y, y)]
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(i, i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b

H, W = inpl()
C = [input() for _ in range(H)]

def calc_cost(L, R):
    global C
    P = [[0]*(H+1) for _ in range(2*H + 1)]
    for l in range(H):
        for r in range(H):
            P[l-r+H][min(l, r)] = int(C[l][L] == C[r][R])

    S = [[0]*(H+1) for _ in range(2*H + 1)]
    for i in range(1, 2*H + 1):
        r = H - abs(H-i)
        for j in range(r):
            S[i][j+1] = S[i][j] + P[i][j]

    DP = [[100000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = S[x-2*y+H][H-max(x-y, y)]
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(i, i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
#def min(a, b): return a if a < b else b

H, W = inpl()
C = [[0]*H for _ in range(W)]
for h in range(H):
    S = input()
    for w in range(W):
        C[w][h] = ord(S[w]) - 97

def calc_cost(L, R):
    P = [[0]*(H+1) for _ in range(2*H + 1)]
    for l in range(H):
        for r in range(H):
            P[l-r+H][min(l, r)] = L[l] == R[r]
    S = [[0]*(H+1) for _ in range(2*H + 1)]
    for i in range(1, 2*H + 1):
        r = H - abs(H-i)
        for j in range(r):
            S[i][j+1] = S[i][j] + P[i][j]

    DP = [[100000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = S[x-2*y+H][H-max(x-y, y)]
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(C[i], C[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b

H, W = inpl()
C = [[0]*H for _ in range(W)]
for h in range(H):
    S = input()
    for w in range(W):
        C[w][h] = ord(S[w]) - 97

def calc_cost(L, R):
    P = [[0]*(H+1) for _ in range(2*H + 1)]
    for l in range(H):
        for r in range(H):
            P[l-r+H][min(l, r)] = L[l] == R[r]
    S = [[0]*(H+1) for _ in range(2*H + 1)]
    for i in range(1, 2*H + 1):
        r = H - abs(H-i)
        for j in range(r):
            S[i][j+1] = S[i][j] + P[i][j]

    DP = [[100000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = S[x-2*y+H][H-max(x-y, y)]
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(C[i], C[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b

H, W = inpl()
C = [[0]*H for _ in range(W)]
for h in range(H):
    S = input()
    for w in range(W):
        C[w][h] = ord(S[w]) - 97

def calc_cost(L, R):
    P = [[0]*(H+1) for _ in range(2*H + 1)]
    for l in range(H):
        for r in range(H):
            P[l-r+H][min(l, r)] = L[l] == R[r]
    S = [[0]*(H+1) for _ in range(2*H + 1)]
    for i in range(1, 2*H + 1):
        r = H - abs(H-i)
        for j in range(r):
            S[i][j+1] = S[i][j] + P[i][j]

    def count(l, r):
        return S[l-r+H][H - max(l, r)]

    DP = [[1000000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = count(x-y, y)
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(C[i], C[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b

H, W = inpl()
C = [[0]*H for _ in range(W)]
for h in range(H):
    S = input()
    for w in range(W):
        C[w][h] = ord(S[w]) - 97

def calc_cost(L, R):
    P = [[0]*(H+1) for _ in range(2*H + 1)]
    for l in range(H):
        for r in range(H):
            P[l-r+H][min(l, r)+1] = L[l] == R[r]
    S = [list(accumulate(p)) for p in P]

    def count(l, r):
        return S[l-r+H][H - max(l, r)]

    DP = [[1000000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = count(x-y, y)
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(C[i], C[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b

H, W = inpl()
C = [[0]*H for _ in range(W)]
for h in range(H):
    S = input()
    for w in range(W):
        C[w][h] = ord(S[w]) - 97

def calc_cost(L, R):
    def count(l, r):
        tmp = 0
        a = max(l-r, 0)
        b = max(r-l, 0)
        for i in range(H-max(l, r)):
            tmp += L[a+i] == R[b+i]
        return tmp
    DP = [[1000000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = count(x-y, y)
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(C[i], C[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b

H, W = inpl()
C = [[0]*H for _ in range(W)]
for h in range(H):
    S = input()
    for w in range(W):
        C[w][h] = ord(S[w]) - 97

def calc_cost(L, R):
    def count(l, r):
        tmp = 0
        a = max(l-r, 0)
        b = max(r-l, 0)
        for i in range(H-max(l, r)):
            tmp += L[a+i] == R[b+i]
        return tmp
    DP = [[1000000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = count(x-y, y)
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    c = calc_cost(C[i], C[i+1])
    ans += calc_cost(C[i], C[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H , W = map(int,input().split())
table = [input() for _ in range(H)]
def memo_rec(a,b,i,j, memo):
    if a == H or b == H:
        return 0
    if memo[a][b] > -1:
        return memo[a][b]
    ret = 0
    tmp = 0
    memo[a][b] = min(memo_rec(a+1,b,i,j, memo= memo), memo_rec(a,b+1,i,j,memo=memo)) + cache[a][b]
#    print("(i,j) = (%d,%d) memo[%d][%d] = %d"% (i,j,a,b,memo[a][b]))
    return memo[a][b]
ans = 0
for i in range(W-1):
#    print("%d,%d"%(i,i+1))
    memo = [[-1 for _ in range(H)] for _ in range(H)]
    cache = [[-1 for _ in range(H+1)] for _ in range(H+1)]
    for a in range(H,-1,-1):
        for b in range(H,-1,-1):
            if a == H or b == H:
                cache[a][b] = 0
            elif table[H-a-1][i] == table[H-b-1][i+1]:
                cache[a][b] = cache[a+1][b+1] + 1
            else :
                cache[a][b] = cache[a+1][b+1]
    ans += (memo_rec(0,0,i,i+1,memo))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
H , W = map(int,input().split())
table = [input() for _ in range(H)]
def memo_rec(a,b,i,j, memo):
    if a == H or b == H:
        return 0
    if memo[a][b] > -1:
        return memo[a][b]
    ret = 0
    tmp = 0 
    for t in range(H):
        if  t - a >= 0 and t - b >= 0:
            if table[t-a][i] == table[t-b][j] :
                tmp += 1
    memo[a][b] = min(memo_rec(a+1,b,i,j, memo= memo), memo_rec(a,b+1,i,j,memo=memo)) + tmp
#    print("(i,j) = (%d,%d) memo[%d][%d] = %d"% (i,j,a,b,memo[a][b]))
    return memo[a][b]
ans = 0
for i in range(W-1):
#    print("%d,%d"%(i,i+1))
    memo = [[-1 for _ in range(H)] for _ in range(H)]
    ans += (memo_rec(0,0,i,i+1,memo))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, raw_input().split())
a = [raw_input().strip() for _ in xrange(H)]
a = map(''.join, zip(*a))
ans = 0
def solve(a, c):
    shift = [[0] * (H+1) for _ in xrange(H+1)]
    for i in reversed(xrange(H)):
        for j in reversed(xrange(H)):
            shift[i][j] = shift[i+1][j+1] + int(a[H-1-i] == c[H-1-j])
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = []
            if i == j == 0:
                b.append(0)
            if i > 0:
                b.append(dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b.append(dp[i][j-1] + shift[i][j-1])
            dp[i][j] = min(b)
    #print a, c, shift
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
X = [list(map(ord,input())) for _ in range(H)]
Y = list(map(list, zip(*X)))


def get(A, B):
    cost = [[0 for _ in range(H + 2)] for _ in range(H + 2)]

    def calc(A, B, a_n, b_n):

        if a_n >= H or b_n >= H:
            return 0

        return cost[a_n][b_n]

    def set_cost(A, B, a_n, b_n):
        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[a_n + H - 1 - i][b_n + H - 1 - i] = ans #cache

    for i in range(H):
        set_cost(A,B,0,i)
        set_cost(A,B,i,0)

    dp = [[999999999999999 for _ in range(H + 2)] for _ in range(H + 2)]
    dp[0][0] = 0

    for i in range(H + 1):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i][j] + calc(A, B, i, j), dp[i + 1][j])
            dp[i][j + 1] = min(dp[i][j] + calc(A, B, i, j), dp[i][j + 1])
    # print(dp)

    return dp[H][H]


ans = 0
for i in range(W - 1):
    tmp = get(Y[i], Y[i + 1])
    ans += tmp
    # print(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
X = [input() for _ in range(H)]
Y = list(map(list, zip(*X)))


def get(A, B):
    cost = [[0 for _ in range(H + 2)] for _ in range(H + 2)]

    def calc(A, B, a_n, b_n):

        if a_n >= H or b_n >= H:
            return 0

        return cost[a_n][b_n]
        
    def set_cost(A, B, a_n, b_n):
        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[a_n + H - 1 - i][b_n + H - 1 - i] = ans #cache

    for i in range(H):
        set_cost(A,B,0,i)
        set_cost(A,B,i,0)

    dp = [[999999999999999 for _ in range(H + 2)] for _ in range(H + 2)]
    dp[0][0] = 0

    for i in range(H + 1):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i][j] + calc(A, B, i, j), dp[i + 1][j])
            dp[i][j + 1] = min(dp[i][j] + calc(A, B, i, j), dp[i][j + 1])
    # print(dp)

    return dp[H][H]


ans = 0
for i in range(W - 1):
    tmp = get(Y[i], Y[i + 1])
    ans += tmp
    # print(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
X = [input() for _ in range(H)]
Y = list(map(list, zip(*X)))


def get(A, B):
    cost = {}

    def calc(A, B, a_n, b_n):
        if a_n >= H or b_n >= H:
            return 0
        if (a_n, b_n) in cost:
            return cost[(a_n, b_n)]
        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[(a_n + H - 1 - i, b_n + H - 1 - i)] = ans
        return cost[(a_n, b_n)]

    for i in range(H):
        calc(A,B,0,i)
        calc(A,B,i,0)

    dp = [[999999999999999 for _ in range(H + 2)] for _ in range(H + 2)]
    dp[0][0] = 0

    for i in range(H + 1):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i][j] + calc(A, B, i, j), dp[i + 1][j])
            dp[i][j + 1] = min(dp[i][j] + calc(A, B, i, j), dp[i][j + 1])
    # print(dp)
    return dp[H][H]


ans = 0
for i in range(W - 1):
    tmp = get(Y[i], Y[i + 1])
    ans += tmp
    # print(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
X = [input() for _ in range(H)]
Y = list(map(list, zip(*X)))


def get(A, B):
    cost = {}

    def calc(A, B, a_n, b_n):
        if a_n >= H or b_n >= H:
            return 0
        if (a_n, b_n) in cost:
            return cost[(a_n, b_n)]

        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[(a_n + H - 1 - i, b_n + H - 1 - i)] = ans
        return cost[(a_n, b_n)]
    for i in range(H):
        calc(A,B,0,i)
        calc(A,B,i,0)

    dp = [[999999999999999 for _ in range(H + 2)] for _ in range(H + 2)]
    dp[0][0] = 0

    for i in range(H + 1):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i][j] + calc(A, B, i, j), dp[i + 1][j])
            dp[i][j + 1] = min(dp[i][j] + calc(A, B, i, j), dp[i][j + 1])
    # print(dp)
    return dp[H][H]


ans = 0
for i in range(W - 1):
    tmp = get(Y[i], Y[i + 1])
    ans += tmp
    # print(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
X= [input() for _  in range(H)]
Y = list(map(list, zip(*X)))

def get(A, B):
    cost ={}
    def calc(A, B, a_n, b_n):
        if a_n < 0 or b_n < 0:
            raise
        if a_n >= H or b_n >= H:
            return 0
        if (a_n,b_n) in cost:
            return cost[(a_n,b_n)]

        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[(a_n+H-1-i,b_n+H-1-i)]=ans
        return cost[(a_n,b_n)]


    dp = [[999999999999999 for _ in range(H+2)] for _ in range(H+2)]
    dp[0][0]=0

    for i in range(H+1):
        for j in range(H+1):
            dp[i+1][j] = min(dp[i][j] + calc(A, B, i  , j), dp[i+1][j])
            dp[i][j+1] = min(dp[i][j] + calc(A, B, i  , j), dp[i][j+1])
    #print(dp)
    return dp[H][H]




ans=0
for i in range(W-1):
    tmp= get(Y[i],Y[i+1])
    ans +=tmp
    #print(tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, raw_input().split())
a = [raw_input().strip() for _ in xrange(H)]
a = map(''.join, zip(*a))
ans = 0
def solve(a, c):
    def shift(i, j):
        ans = 0
        for pos in xrange(max(i, j), H):
            if a[pos - i] == c[pos - j]:
                ans += 1
        return ans
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    shift_ = [[None] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            shift_[i][j] = shift(i, j)
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = []
            if i == j == 0:
                b.append(0)
            if i > 0:
                b.append(dp[i-1][j] + shift_[i-1][j])
            if j > 0:
                b.append(dp[i][j-1] + shift_[i][j-1])
            dp[i][j] = min(b)
    #print a, c, shift_
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, raw_input().split())
A = []
d = dict()
 
for h in range(H):
    A.append(list(raw_input()))
 
# breadth first search
que = [[0]*W]
 
d[str([0]*W)] = 0
ind = 0
 
while True:
    if ind >= len(que):
        break
    q = que[ind]
    ind += 1
    for w in range(W):
        if q[w] < H:
            q_ = list(q)
            q_[w] += 1
            cost = d[str(q)]
            # add cost
            if w != 0:
                # left
                if q[w-1] < q[w]:
                    for j in range(H - q[w]):
                        if A[j][w] == A[j - q[w-1] + q[w]][w-1]:
                            cost += 1
                else:
                    for j in range(H - q[w-1]):
                        if A[j + q[w-1] - q[w]][w] == A[j][w-1]:
                            cost += 1
            if w != W-1:
                # right
                if q[w+1] < q[w]:
                    for j in range(H - q[w]):
                        if A[j][w] == A[j - q[w+1] + q[w]][w+1]:
                            cost += 1
                else:
                    for j in range(H - q[w+1]):
                        if A[j + q[w+1] - q[w]][w] == A[j][w+1]:
                            cost += 1
            if d.has_key(str(q_)):
                if d[str(q_)] > cost:
                    d[str(q_)] = cost
                    que.append(q_)
                else:
                    pass
            else:
                d[str(q_)] = cost
                que.append(q_)
        else:
            pass
        
print d[str([H]*W)]

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, raw_input().split())
A = []
d = dict()

for h in range(H):
    A.append(list(raw_input()))

# breadth first search
que = [[0]*W]

d[str([0]*W)] = 0
ind = 0

while True:
    if ind >= len(que):
        break
    q = que[ind]
    ind += 1
    for w in range(W):
        if q[w] < H:
            q_ = list(q)
            q_[w] += 1
            cost = d[str(q)]
            # add cost
            if w != 0:
                # left
                if q[w-1] < q[w]:
                    for j in range(H - q[w]):
                        if A[j][w] == A[j - q[w-1] + q[w]][w-1]:
                            cost += 1
                else:
                    for j in range(H - q[w-1]):
                        if A[j + q[w-1] - q[w]][w] == A[j][w-1]:
                            cost += 1
            if w != W-1:
                # right
                if q[w+1] < q[w]:
                    for j in range(H - q[w]):
                        if A[j][w] == A[j - q[w+1] + q[w]][w+1]:
                            cost += 1
                else:
                    for j in range(H - q[w+1]):
                        if A[j + q[w+1] - q[w]][w] == A[j][w+1]:
                            cost += 1
            if d.has_key(str(q_)):
                if d[str(q_)] > cost:
                    d[str(q_)] = cost
                    que.append(q_)
                else:
                    pass
            else:
                d[str(q_)] = cost
                que.append(q_)
        else:
            pass
        
print d[str([H]*W)]

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = map(int, raw_input().split())
blocks = [raw_input() for i in xrange(H)]

cnt = 0

ma = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]
dp = [[0 for i in xrange(H + 1)] for j in xrange(H + 1)]

for n in range(W - 1):
    for i in range(H):
        for j in range(H):
            ma[i + 1][j + 1] = ma[i][j]
            if blocks[i][n] == blocks[j][n + 1]:
                ma[i + 1][j + 1] += 1
    
    for i in range(H):
        for j in range(H):
            dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + ma[i + 1][j + 1]
    
    cnt += dp[-1][-1]

print cnt

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
c = [input().rstrip() for _ in range(H)]
ans = 0
for w in range(W-1):
    cum1 = [[0] * (H + 1) for _ in range(H + 1)]
    for d in range(H):
        for i in range(H - d):
            cum1[d][i+1] = cum1[d][i] + (c[i][w] == c[d+i][w+1])
    cum2 = [[0] * (H + 1) for _ in range(H + 1)]
    for d in range(H):
        for i in range(H - d):
            cum2[d][i+1] = cum2[d][i] + (c[d+i][w] == c[i][w+1])
    dp = [[0] * (H + 1) for _ in range(H + 1)]
    for i in range(1, H+1):
        for j in range(1, H+1):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            if i >= j:
                dp[i][j] += cum1[i-j][j]
            else:
                dp[i][j] += cum2[j-i][i]
    ans += dp[H][H]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
c = [None]*h
for i in range(h):
    c[i] = input()
# def sub(i):
#     c0 = c[i]
#     c1 = c[i+1]
#     dp = [[None]*(h+1) for _ in range(h+1)]
#     for i in range(h+1):
#         dp[i][0] = 0
#         dp[0][i] = 0
#     val = [None]*(2*h+1) # c0がc1よりi-h高いときの衝突数の累積和
#     for i in range(h):
#         # c1がh, c0がi
#         l = []
#         v = 0
#         for j in range(i):
#             if c1[h-i+j]==c0[j]:
#                 v += 1
#             l.append(v)
#         val[i] = l
#     for i in range(h, -1, -1):
#         # c0がh, c1がi
#         l = []
#         v = 0
#         for j in range(i):
#             if c0[h-i+j]==c1[j]:
#                 v += 1
#             l.append(v)
#         val[h+(h-i)] = l
        
#     for i in range(1, h+1):
#         for j in range(1, h+1):
#             dp[i][j] = min(dp[i+1][j]+val[(i+1)-j+h][i], dp[i][j+1]+val[i-(j+1)+h][i-1])
#     return dp[h][h]
ans = 0
for i in range(w-1):
    c0 = [c[j][i] for j in range(h)]
    c1 = [c[j][i+1] for j in range(h)]
    dp = [[None]*(h+1) for _ in range(h+1)]
    for i in range(h+1):
        dp[i][0] = 0
        dp[0][i] = 0
    val = [None]*(2*h+1) # c0がc1よりi-h高いときの衝突数の累積和
    for i in range(h):
        # c1がh, c0がi
        l = []
        v = 0
        for j in range(i):
            if c1[h-i+j]==c0[j]:
                v += 1
            l.append(v)
        val[i] = l
    for i in range(h, -1, -1):
        # c0がh, c1がi
        l = []
        v = 0
        for j in range(i):
            if c0[h-i+j]==c1[j]:
                v += 1
            l.append(v)
        val[h+(h-i)] = l
        
    for i in range(1, h+1):
        for j in range(1, h+1):
            cost = val[(i)-j+h][min(i,j)-1]
            dp[i][j] = min(dp[i-1][j]+cost, dp[i][j-1]+cost)
    ans += dp[h][h]
#     return dp[h][h]

#     ans += sub(i)
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
c = [input() for _ in range(h)]

ans = 0
for i in range(w-1):
    cost = [[0] * (h+1) for _ in range(h+1)]
    for ci in range(1,h+1):
        for cj in range(ci,h+1):
            cost[ci][cj] = cost[ci-1][cj-1] + (c[ci-1][i] == c[cj-1][i+1])

    for cj in range(1,h+1):
        for ci in range(cj+1,h+1):
            cost[ci][cj] = cost[ci-1][cj-1] + (c[ci-1][i] == c[cj-1][i+1])

    dp = [[0] * (h+1) for _ in range(h+1)]
    for ci in range(1,h+1):
        for cj in range(1,h+1):
            dp[ci][cj] = min(dp[ci-1][cj], dp[ci][cj-1]) + cost[ci][cj]

    ans += dp[-1][-1]

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
c=[input() for i in range(H)]
res=0
for i in range(W-1):
    dp=[[0 for j in range(H+1)] for k in range(H+1)]
    table=[[0 for j in range(H+1)] for k in range(H+1)]
    for j in range(1,H+1):
        for k in range(1,H+1):
            table[j][k]=table[j-1][k-1]+(c[j-1][i]==c[k-1][i+1])

    for j in range(1,H+1):
        for k in range(1,H+1):
            cost=table[j][k]
            dp[j][k]=cost+min(dp[j-1][k],dp[j][k-1])
    res+=dp[H][H]

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**10
h, w = map(int, input().split())
C = [input().rstrip() for _ in range(h)]
def solve(b):
  cost = [[0]*(h+1) for _ in range(h+1)]
  dp = [[INF]*(h+1) for _ in range(h+1)]
  dp[0][0] = 0
  for i in range(h+1):
    for j in range(h+1):
      if i and j:
        cost[i][j] = cost[i-1][j-1] - (C[h-i][b] == C[h-j][b+1])
      else:
        for r in range(min(h-i, h-j)):
          cost[i][j] += C[j+r][b] == C[i+r][b+1]
      if i:
        dp[i][j] = min(dp[i][j], dp[i-1][j]+cost[i-1][j])
      if j:
        dp[i][j] = min(dp[i][j], dp[i][j-1]+cost[i][j-1])
  return dp[h][h]
ans = 0
for b in range(w-1):
  ans += solve(b)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [input().rstrip() for i in range(n)]
b = list(zip(*a))
for i in range(m):
  b[i] = "".join(b[i])
ans = 0
ct1 = [[0 for k in range(n-j+1)] for j in range(n+1)]
ct2 = [[0 for k in range(n-j+1)] for j in range(n+1)]
dp = [[10**5 for i in range(n+1)] for j in range(n+1)]
for i in range(m-1):
  b1 = b[i]
  b2 = b[i+1]
  for j in range(n+1):
    ct1[j][0] = 0
    ct2[j][0] = 0
    for k in range(n-j):
      ct1[j][k+1] = ct1[j][k]
      ct2[j][k+1] = ct2[j][k]
      if b1[k+j] == b2[k]:
        ct1[j][k+1] += 1
      if b2[k+j] == b1[k]:
        ct2[j][k+1] += 1
  dp[0][0] = 0
  for i in range(n+1):
    if i < n:
      dp[i+1][0] = 10**6
    for j in range(n+1):
      if i == 0 and j < n:
        dp[i][j+1] = 10**6
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
      if i < n:
        dp[i+1][j] = dp[i][j]+cost
  ans += dp[-1][-1]
print(ans)