Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HR = list(range(h))
WR = list(range(w))

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WR] for _ in HR]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WR] for _ in HR]  # ver[top][left][right] = bottom

for i in HR:
    hi = hor[i]
    fi = field[i]
    curr = hi[-1][i] = w - 1
    for j in range(w - 2, -1, -1):
        if fi[j] != fi[j + 1]:
            curr = hi[j][i] = j
        else:
            hi[j][i] = curr

for i in HR:
    hi = hor[i]
    vi = ver[i]
    fi = field[i]
    for j in WR:
        hij = hi[j]
        vij = vi[j]
        fij = fi[j]
        curr = hij[i]
        for k in range(i + 1, h):
            if field[k][j] != fij:
                break
            curr = hij[k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            if hij[k] == -1:
                continue
            nxtr = hij[k] + 1
            dr = nxtr - curr
            if dr > 0:
                vij[curr:nxtr] = [k] * dr
                curr = nxtr

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in HR:
        hi = hor[i]
        vi = ver[i]
        for j in WR:
            hij = hi[j]
            vij = vi[j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in range(i, h):
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hi[h_ijk + 1][k])
            for k in range(j, w):
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                for l in range(curr, h_ijk + 1):
                    vij[l] = max(vij[l], k)
                curr = h_ijk + 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                for l in range(curb, v_ijk + 1):
                    hij[l] = max(hij[l], k)
                curb = v_ijk + 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)


Fixed submission:
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HR = list(range(h))
WR = list(range(w))
WR2 = list(range(w - 2, -1, -1))

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WR] for _ in HR]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WR] for _ in HR]  # ver[top][left][right] = bottom

for i in HR:
    hi = hor[i]
    fi = field[i]
    curr = hi[-1][i] = w - 1
    curc = fi[-1]
    for j in WR2:
        if fi[j] != curc:
            curr = hi[j][i] = j
            curc = fi[j]
        else:
            hi[j][i] = curr

for i in HR:
    hi = hor[i]
    vi = ver[i]
    fi = field[i]
    for j in WR:
        hij = hi[j]
        vij = vi[j]
        fij = fi[j]
        curr = hij[i]
        for k in range(i + 1, h):
            if field[k][j] != fij:
                break
            curr = hij[k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            if hij[k] == -1:
                continue
            nxtr = hij[k] + 1
            dr = nxtr - curr
            if dr > 0:
                vij[curr:nxtr] = [k] * dr
                curr = nxtr

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in HR:
        hi = hor[i]
        vi = ver[i]
        for j in WR:
            hij = hi[j]
            vij = vi[j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in range(i, h):
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hi[h_ijk + 1][k])
            for k in range(j, w):
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                while curr <= h_ijk:
                    vij[curr] = max(vij[curr], k)
                    curr += 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                while curb <= v_ijk:
                    hij[curb] = max(hij[curb], k)
                    curb += 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HI = [0] * h
WI = [0] * w

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WI] for _ in HI]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WI] for _ in HI]  # ver[top][left][right] = bottom

for i in range(h):
    curr = hor[i][-1][i] = w - 1
    for j in range(w - 2, -1, -1):
        if field[i][j] != field[i][j + 1]:
            curr = hor[i][j][i] = j
        else:
            hor[i][j][i] = curr

for i in range(h):
    for j in range(w):
        curr = hor[i][j][i]
        top_left = field[i][j]
        for k in range(i + 1, h):
            if field[k][j] != top_left:
                break
            curr = hor[i][j][k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            if hor[i][j][k] == -1:
                continue
            nxtr = hor[i][j][k] + 1
            dr = nxtr - curr
            if dr > 0:
                ver[i][j][curr:nxtr] = [k] * dr
                curr = nxtr

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in range(h):
        for j in range(w):
            hij = hor[i][j]
            vij = ver[i][j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in range(i, h):
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hor[i][h_ijk + 1][k])
            for k in range(j, w):
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                for l in range(curr, h_ijk + 1):
                    vij[l] = max(vij[l], k)
                curr = h_ijk + 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                for l in range(curb, v_ijk + 1):
                    hij[l] = max(hij[l], k)
                curb = v_ijk + 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)


Fixed submission:
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HR = list(range(h))
WR = list(range(w))
WR2 = list(range(w - 2, -1, -1))

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WR] for _ in HR]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WR] for _ in HR]  # ver[top][left][right] = bottom

for i in HR:
    hi = hor[i]
    fi = field[i]
    curr = hi[-1][i] = w - 1
    curc = fi[-1]
    for j in WR2:
        if fi[j] != curc:
            curr = hi[j][i] = j
            curc = fi[j]
        else:
            hi[j][i] = curr

for i in HR:
    hi = hor[i]
    vi = ver[i]
    fi = field[i]
    for j in WR:
        hij = hi[j]
        vij = vi[j]
        fij = fi[j]
        curr = hij[i]
        for k in range(i + 1, h):
            if field[k][j] != fij:
                break
            curr = hij[k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            if hij[k] == -1:
                continue
            nxtr = hij[k] + 1
            dr = nxtr - curr
            if dr > 0:
                vij[curr:nxtr] = [k] * dr
                curr = nxtr

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in HR:
        hi = hor[i]
        vi = ver[i]
        for j in WR:
            hij = hi[j]
            vij = vi[j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in range(i, h):
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hi[h_ijk + 1][k])
            for k in range(j, w):
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                while curr <= h_ijk:
                    vij[curr] = max(vij[curr], k)
                    curr += 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                while curb <= v_ijk:
                    hij[curb] = max(hij[curb], k)
                    curb += 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)