Problem:
 Score : 1000 points    Problem Statement Note the unusual memory limit.  For a rectangular grid where each square is painted white or black, we define its complexity as follows:   If all the squares are black or all the squares are white, the complexity is 0 .  Otherwise, divide the grid into two subgrids by a line parallel to one of the sides of the grid, and let c_1 and c_2 be the complexities of the subgrids. There can be multiple ways to perform the division, and let m be the minimum value of \max(c_1, c_2) in those divisions. The complexity of the grid is m+1 .   You are given a grid with H horizontal rows and W vertical columns where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is # if the square at the i -th row from the top and the j -th column from the left is black, and A_{ij} is . if that square is white.  Find the complexity of the given grid.      Constraints  1 \leq H,W \leq 185  A_{ij} is # or . .         Input Input is given from Standard Input in the following format:  H  W  A_{11} A_{12} ... A_{1W}  :  A_{H1} A_{H2} ... A_{HW}       Output Print the complexity of the given grid.        Sample Input 1 3 3
...
.##
.##      Sample Output 1 2  Let us divide the grid by the boundary line between the first and second columns.
The subgrid consisting of the first column has the complexity of 0 , and the subgrid consisting of the second and third columns has the complexity of 1 , so the whole grid has the complexity of at most 2 .       Sample Input 2 6 7
.####.#
#....#.
#....#.
#....#.
.####.#
#....##      Sample Output 2 4

Solution (Python):
H, W = map(int, input().split())
A = [[1 if a == "
X = [[[-2] * (H + 2) for _ in range(W + 2)] for _ in range(H + 2)]
Y = [[[-2] * (W + 2) for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H):
    Xi = X[i]
    Yi = Y[i]
    for j in range(W):
        Xi[j][i] = j
        Yi[j][j] = i
for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W-1)[::-1]:
        if Ai[j] == Ai[j+1]:
            Xi[j][i] = Xi[j+1][i]
for i in range(H-1)[::-1]:
    Yi = Y[i]
    Yi1 = Y[i+1]
    Ai = A[i]
    Ai1 = A[i+1]
    for j in range(W):
        if Ai[j] == Ai1[j]:
            Yi[j][j] = Yi1[j][j]

for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W):
        Xij = Xi[j]
        for ii in range(i+1, H):
            if A[ii][j] != Ai[j]:
                break
            Xij[ii] = min(Xij[ii-1], X[ii][j][ii])
for i in range(H):
    Yi = Y[i]
    Ai = A[i]
    for j in range(W):
        Yij = Yi[j]
        for jj in range(j+1, W):
            if Ai[jj] != Ai[j]:
                break
            Yij[jj] = min(Yij[jj-1], Yi[jj][jj])

for k in range(16):
    if X[0][0][H-1] == W-1:
        print(k)
        break
    elif k == 15:
        print(16)
        break
    for i in range(H):
        Xi = X[i]
        Yi = Y[i]
        for j in range(W):
            Xij = Xi[j]
            Yij = Yi[j]
            for ii in range(i, H):
                Xijii = Xij[ii]
                if Xijii >= 0 and X[i][Xijii + 1][ii] >= 0:
                    Xij[ii] = X[i][Xijii + 1][ii]
            for jj in range(j, W):
                Yijjj = Yij[jj]
                if Yijjj >= 0 and Y[Yijjj + 1][j][jj] >= 0:
                    Yij[jj] = Y[Yijjj + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Yij[jj] < ii:
                    jj -= 1
                if j <= jj > Xij[ii]:
                    Xij[ii] = jj
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and Xij[ii] < jj:
                    ii -= 1
                if i <= ii > Yij[jj]:
                    Yij[jj] = ii

Solution (Python):
H, W = map(int, input().split())
A = [[1 if a == "
X = [[[-2] * (H + 2) for _ in range(W + 2)] for _ in range(H + 2)]
Y = [[[-2] * (W + 2) for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H):
    Xi = X[i]
    Yi = Y[i]
    for j in range(W):
        Xi[j][i] = j
        Yi[j][j] = i
for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W-1)[::-1]:
        if Ai[j] == Ai[j+1]:
            Xi[j][i] = Xi[j+1][i]
for i in range(H-1)[::-1]:
    Yi = Y[i]
    Yi1 = Y[i+1]
    Ai = A[i]
    Ai1 = A[i+1]
    for j in range(W):
        if Ai[j] == Ai1[j]:
            Yi[j][j] = Yi1[j][j]

for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W):
        Xij = Xi[j]
        for ii in range(i+1, H):
            if A[ii][j] != Ai[j]:
                break
            Xij[ii] = min(Xij[ii-1], X[ii][j][ii])
for i in range(H):
    Yi = Y[i]
    Ai = A[i]
    for j in range(W):
        Yij = Yi[j]
        for jj in range(j+1, W):
            if Ai[jj] != Ai[j]:
                break
            Yij[jj] = min(Yij[jj-1], Yi[jj][jj])

for k in range(16):
    if X[0][0][H-1] == W-1:
        print(k)
        break
    elif k == 15:
        print(16)
        break
    for i in range(H):
        Xi = X[i]
        Yi = Y[i]
        for j in range(W):
            Xij = Xi[j]
            Yij = Yi[j]
            for ii in range(i, H):
                Xijii = Xij[ii]
                if Xijii >= 0 and X[i][Xijii + 1][ii] >= 0:
                    Xij[ii] = X[i][Xijii + 1][ii]
            for jj in range(j, W):
                Yijjj = Yij[jj]
                if Yijjj >= 0 and Y[Yijjj + 1][j][jj] >= 0:
                    Yij[jj] = Y[Yijjj + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Yij[jj] < ii:
                    jj -= 1
                if jj >= j:
                    Xij[ii] = max(Xij[ii], jj)
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and Xij[ii] < jj:
                    ii -= 1
                if ii >= i:
                    Yij[jj] = max(Yij[jj], ii)

Solution (Python):
H, W = map(int, input().split())
A = [[1 if a == "
X = [[[-2] * (H + 2) for _ in range(W + 2)] for _ in range(H + 2)]
Y = [[[-2] * (W + 2) for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H):
    for j in range(W):
        X[i][j][i] = j
        Y[i][j][j] = i
for i in range(H):
    for j in range(W-1)[::-1]:
        if A[i][j] == A[i][j+1]:
            X[i][j][i] = X[i][j+1][i]
for i in range(H-1)[::-1]:
    for j in range(W):
        if A[i][j] == A[i+1][j]:
            Y[i][j][j] = Y[i+1][j][j]

for i in range(H):
    for j in range(W):
        for ii in range(i+1, H):
            if A[ii][j] != A[i][j]:
                break
            X[i][j][ii] = min(X[i][j][ii-1], X[ii][j][ii])
for i in range(H):
    for j in range(W):
        for jj in range(j+1, W):
            if A[i][jj] != A[i][j]:
                break
            Y[i][j][jj] = min(Y[i][j][jj-1], Y[i][jj][jj])

for k in range(16):
    if X[0][0][H-1] == W-1:
        print(k)
        break
    elif k == 15:
        print(16)
        break
    for i in range(H):
        Xi = X[i]
        Yi = Y[i]
        for j in range(W):
            Xij = Xi[j]
            Yij = Yi[j]
            for ii in range(i, H):
                Xijii = Xij[ii]
                if Xijii >= 0 and X[i][Xijii + 1][ii] >= 0:
                    Xij[ii] = X[i][Xijii + 1][ii]
            for jj in range(j, W):
                Yijjj = Yij[jj]
                if Yijjj >= 0 and Y[Yijjj + 1][j][jj] >= 0:
                    Yij[jj] = Y[Yijjj + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Yij[jj] < ii:
                    jj -= 1
                if jj >= j:
                    Xij[ii] = max(Xij[ii], jj)
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and Xij[ii] < jj:
                    ii -= 1
                if ii >= i:
                    Yij[jj] = max(Yij[jj], ii)

Solution (Python):
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))


hor = [[[-1] * h for _ in WR] for _ in HR]  
ver = [[[-1] * w for _ in WR] for _ in HR]  

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 HR[i + 1:]:
            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):
            h_ijk = hij[k]
            if h_ijk == -1:
                continue
            while curr <= h_ijk:
                vij[curr] = k
                curr += 1

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]

            
            
            

            
            for k in HR[i:]:
                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 WR[j:]:
                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])

            
            
            

            
            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

            
            
            
    ans += 1

print(ans)

Solution (Python):
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))


hor = [[[-1] * h for _ in WR] for _ in HR]  
ver = [[[-1] * w for _ in WR] for _ in HR]  

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]

            
            
            

            
            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])

            
            
            

            
            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

            
            
            
    ans += 1

print(ans)