Buggy python submission (verdict: Time Limit Exceeded):
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


Fixed submission:
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 = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = 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

Buggy python submission (verdict: Time Limit Exceeded):
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


Fixed submission:
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 = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = 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

Buggy python submission (verdict: Runtime Error):
class Bit:
    def __init__(self, n):
        sz = 1
        while n >= sz:
            sz *= 2
        self.size = sz
        self.data = [0]*sz

    def sum(self, i):
        assert i > 0
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        assert i > 0
        while i < self.size:
            self.data[i] += x
            i += i & -i

import bisect
N = int(raw_input())
a = [int(x)-1 for x in raw_input().split()]
weight = [1] * N
M = 10**9+7
def factorial(n):
    acc = 1
    for i in xrange(1, 1 + n):
        acc = (acc * i) % M
    return acc
def inv(n):
    return pow(n, M-2, M)
for i in xrange(N-1):
    weight[N-2-i] = (weight[N-1-i] * (i+1)) % M
missing = list(set(xrange(N)) - set(a))
missing.sort()
n_missing = len(missing)
sum_missing = sum(missing)
avg_missing = sum_missing * inv(n_missing)
n_present = N - n_missing
n_rows = factorial(n_missing)
acc = 0
i_missing = 0
i_present = 0
missing_lt_tot = 0
#present_values = []
present_values_bit = Bit(N+5)
inv_n_missing = inv(n_missing)
inv_2 = inv(2)
for i, (w, x) in enumerate(zip(weight, a)):
    if x == -1:
        ai = avg_missing
        bi = (i_missing * inv_2 + i_present - missing_lt_tot * inv_n_missing) % M
        i_missing += 1
    else:
        ai = x
        #bi = sum(1 for present_value in present_values if present_value < x)
        bi = present_values_bit.sum(x + 1)
        #present_values.append(x)
        present_values_bit.add(x + 2, 1)
        '''
        missing_lt = 0
        for j in missing:
            if j < a[i]:
                missing_lt += 1
        '''
        missing_lt = bisect.bisect(missing, a[i])
        missing_lt_tot += missing_lt
        #print '@', missing_lt, n_missing, i_missing, n_rows
        bi += missing_lt * inv_n_missing * i_missing
        bi %= M
        i_present += 1
    #print x, (ai * n_rows) % M, (bi * n_rows) % M, w
    acc = (acc + (((ai - bi) * n_rows) % M) * w) % M
print (acc + n_rows) % M


Fixed submission:
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 = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = 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

Buggy python submission (verdict: Time Limit Exceeded):
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


Fixed submission:
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 = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = 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