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



Sample input:
3 3
...
.##
.##


Sample output:
2

Submission status: Wrong Answer

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

h_cnt = 1
for i in range(h-1):
    if any(a[i][j] != a[i+1][j] for j in range(w)):
        h_cnt += 1

w_cnt = 1
for j in range(w-1):
    if any(a[i][j] != a[i][j+1] for i in range(h)):
        w_cnt += 1

x = h_cnt * w_cnt
for i in range(100):
    if 2 ** (i-1) < x <= 2 ** i:
        print(i)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
G = []
for i in range(h):
  G.append(input())
l = []
for i in range(h):
  cnt = 0
  for j in range(w-1):
    if G[i][j+1] != G[i][j]:
      cnt += 1
  cnt = (cnt+2)//2
  if i == 0:
    l.append(cnt)
  elif i > 0 and G[i] == G[i-1]:
    continue
  else:
    l.append(cnt)
ans = max(l)+len(l)-1
if len(l) >= 3:
  for i in range(1, len(l)-1):
    ans = min(ans, max(max(l[:i])+i, max(l[i:])+len(l)-1-i))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
G = []
for i in range(h):
  G.append(input())
dp = [0 for i in range(h)]
for i in range(h):
  cnt = 0
  for j in range(w-1):
    if G[i][j+1] != G[i][j]:
      cnt += 1
  if i == 0:
    dp[i] = cnt
  elif i > 0 and G[i] == G[i-1]:
    dp[i] = dp[i-1]
  else:
    dp[i] = max(dp[i-1], cnt+1)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
H,W=map(int,input().split())
A=[]

for i in range(H):
    line=list(input())
    A.append(line)


ROW=[0 for i in range(W-1)]
LINE=[0 for i in range(H-1)]

for i in range(H):
    for j in range(1,W):
        if A[i][j-1]!=A[i][j]:
            ROW[j-1]=1
            
for i in range(1,H):
    for j in range(W):
        if A[i-1][j]!=A[i][j]:
            LINE[i-1]=1



ans=0

B=sum(ROW)+1

while B>1:
    B=B/2
    ans+=1
    
B=sum(LINE)+1

while B>1:
    B=B/2
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
H,W=map(int,input().split())
A=[]

for i in range(H):
    line=list(input())
    A.append(line)


ROW=[0 for i in range(W-1)]
LINE=[0 for i in range(H-1)]

for i in range(H):
    for j in range(1,W):
        if A[i][j-1]!=A[i][j]:
            ROW[j-1]=1
            
for i in range(1,H):
    for j in range(W):
        if A[i-1][j]!=A[i][j]:
            LINE[i-1]=1

B=(sum(ROW)+1)*(sum(LINE)+1)

ans=0

while B>1:
    B=B/2
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
S=[input() for _ in range(H)]

paint=((1,0),(-1,0),(0,1),(0,-1))
que=deque([])

dark=[[0]*W for _ in range(H)] # 1が黒、0はまだ白

for i in range(H): # 初期化(最初に黒いマスをdarkリストに入れて、キューに入れる。)
    for j in range(W):
        if S[i][j]=='#':
            que.append((i,j,0))
            dark[i][j]=1
ans=0
while len(que)>0:
    di,dj,c=que.popleft()
    
    for pi,pj in paint:
        ni,nj=pi+di,pj+dj # 移動先がni,nj
        if 0<=ni<H and 0<=nj<W and dark[ni][nj]==0:
            dark[ni][nj]=1
            que.append((ni,nj,c+1))
            ans=c+1
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
L=[]
A=list(input())
L.append(A)
cnt1=0
for i in range(H-1):
    A=list(input())
    if L[-1]!=A:
        cnt1+=1
        L.append(A)
#print(L)
#print(cnt1)
cnt2=0
for i in range(len(L)):
    cnt=0
    F=L[i][0]
    for j in range(1,W):
        if F!=L[i][j]:
            cnt+=1
            F=L[i][j]
    if cnt2<cnt:
        cnt2=cnt
#print(cnt2)
ans=0
for i in range(10):
    if cnt1<2**i:
        ans+=i
        break
for i in range(10):
    if cnt2<2**i:
        ans+=i
        break
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    h,w=map(int,input().split())
    grid=[input() for _ in [0]*h]
    yoko=[[[0]*w for _ in [0]*(h-i)] for i in range(h)] #上、下、横
    tate=[[[0]*h for _ in [0]*(w-i)] for i in range(w)] #左、右、縦
    
    #初期化
    
    for i in range(h):
        cnt=2
        yoko[i][0][w-1]=1
        for j in range(w-2,-1,-1):
            if grid[i][j]==grid[i][j+1]:
                yoko[i][0][j]=cnt
                cnt+=1
            else:
                yoko[i][0][j]=1
                cnt=2
    for i in range(w):
        cnt=2
        tate[i][0][h-1]=1
        for j in range(h-2,-1,-1):
            if grid[j+1][i]==grid[j][i]:
                tate[i][0][j]=cnt
                cnt+=1
            else:
                tate[i][0][j]=1
                cnt=2
    
    for k in range(w):
        for i in range(h-1):
            m=yoko[i][0][k]
            for j in range(1,h-i):
                if grid[i+j][k]!=grid[i+j-1][k]:
                    break
                m=min(yoko[i+j][0][k],m)
                yoko[i][j][k]=m
    
    for k in range(h):
        for i in range(w-1):
            m=tate[i][0][k]
            for j in range(1,w-i):
                if grid[k][i+j]!=grid[k][i+j-1]:
                    break
                m=min(tate[i+j][0][k],m)
                tate[i][j][k]=m
    
    #終わるまでやる
    #yoko= #上、下、横
    #tate= #左、右、縦
    for c in range(1,18):
        if yoko[0][h-1][0]==w or tate[0][w-1][0]==h:
            print(c-1)
            break
        yoko2=[[[0]*w for _ in [0]*(h-i)] for i in range(h)]
        tate2=[[[0]*h for _ in [0]*(w-i)] for i in range(w)]
        for i in range(h):
            for j in range(h-i):
                for k in range(w):
                    temp=yoko[i][j][k]
                    if temp+k==w:
                        yoko2[i][j][k]=temp
                    else:
                        yoko2[i][j][k]=max(temp+yoko[i][j][k+temp],yoko2[i][j][k])
                    if j!=h-i-1:
                        temp2=tate[k][temp-1][i+j+1]#
                        yoko2[i][j+temp2][k]=max(temp,yoko2[i][j+temp2][k])
        
        for i in range(w):
            for j in range(w-i):
                for k in range(h):
                    temp=tate[i][j][k]
                    if temp+k==h:
                        tate2[i][j][k]=temp
                    else:
                        tate2[i][j][k]=max(temp+tate[i][j][k+temp],tate2[i][j][k])
                    if j!=w-i-1:
                        temp2=yoko[k][temp-1][i+j+1]
                        tate2[i][j+temp2][k]=max(temp,tate2[i][j+temp2][k])
        yoko=yoko2
        tate=tate2
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    h,w=map(int,input().split())
    grid=[input() for _ in [0]*h]
    yoko=[[[0]*w for _ in [0]*(h-i)] for i in range(h)] #複雑度、上、下、横
    tate=[[[0]*h for _ in [0]*(w-i)] for i in range(w)] #複雑度、左、右、縦
    
    #初期化
    
    for i in range(h):
        cnt=2#2つ目のiは全部iを引く
        yoko[i][0][w-1]=1
        for j in range(w-2,-1,-1):
            if grid[i][j]==grid[i][j+1]:
                yoko[i][0][j]=cnt
                cnt+=1
            else:
                yoko[i][0][j]=1
                cnt=2
    for i in range(w):
        cnt=2
        tate[i][0][h-1]=1
        for j in range(h-2,-1,-1):
            if grid[j+1][i]==grid[j][i]:
                tate[i][0][j]=cnt
                cnt+=1
            else:
                tate[i][0][j]=1
                cnt=2
    
    for k in range(w):
        for i in range(h-1):
            m=yoko[i][0][k]
            for j in range(1,h-i):
                if grid[i+j][k]!=grid[i+j-1][k]:
                    break
                m=min(yoko[i+j][0][k],m)
                yoko[i][j][k]=m
    
    for k in range(h):
        for i in range(w-1):
            m=tate[i][0][k]
            for j in range(1,w-i):
                if grid[k][i+j]!=grid[k][i+j-1]:
                    break
                m=min(tate[i+j][0][k],m)
                tate[i][j][k]=m
    
    #終わるまでやる
    #yoko= #複雑度、上、下、横
    #tate= #複雑度、左、右、縦
    for c in range(1,18):
        if yoko[0][h-1][0]==w:
            print(c-1)
            break
        yoko2=[[[0]*w for _ in [0]*(h-i)] for i in range(h)] #複雑度、上、下、横
        tate2=[[[0]*h for _ in [0]*(w-i)] for i in range(w)] #複雑度、左、右、縦
        for i in range(h):
            for j in range(h-i):
                for k in range(w):
                    temp=yoko[i][j][k]
                    if temp+k==w:
                        yoko2[i][j][k]=temp
                    else:
                        yoko2[i][j][k]=max(temp+yoko[i][j][k+temp],yoko2[i][j][k])
                    if j!=h-i-1:
                        temp2=tate[k][temp-1][i+j+1]
                        yoko2[i][j+temp2][k]=max(temp,yoko2[i][j+temp2][k])
        
        for i in range(w):
            for j in range(w-i):
                for k in range(h):
                    temp=tate[i][j][k]
                    if temp+k==h:
                        tate2[i][j][k]=temp
                    else:
                        tate2[i][j][k]=max(temp+tate[i][j][k+temp],tate2[i][j][k])
                    if j!=w-i-1:
                        temp2=yoko[k][temp-1][i+j+1]
                        tate2[i][j+temp2][k]=max(temp,tate2[i][j+temp2][k])
        yoko=yoko2
        tate=tate2
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    h,w=map(int,input().split())
    grid=[input() for _ in [0]*h]
    yoko=[[[[0]*w for _ in [0]*h] for _ in [0]*h] for _ in [0]*17] #複雑度、上、下、横
    tate=[[[[0]*h for _ in [0]*w] for _ in [0]*w] for _ in [0]*17] #複雑度、左、右、縦
    
    #初期化
    
    for i in range(h):
        cnt=2
        yoko[0][i][i][w-1]=1
        for j in range(w-2,-1,-1):
            if grid[i][j]==grid[i][j+1]:
                yoko[0][i][i][j]=cnt
                cnt+=1
            else:
                yoko[0][i][i][j]=1
                cnt=2
    for i in range(w):
        cnt=2
        tate[0][i][i][h-1]=1
        for j in range(h-2,-1,-1):
            if grid[j+1][i]==grid[j][i]:
                tate[0][i][i][j]=cnt
                cnt+=1
            else:
                tate[0][i][i][j]=1
                cnt=2
    
    for k in range(w):
        for i in range(h-1):
            m=yoko[0][i][i][k]
            for j in range(i+1,h-1):
                if grid[j][k]!=grid[j-1][k]:
                    break
                m=min(yoko[0][j][j][k],m)
                yoko[0][i][j][k]=m
    
    for k in range(h):
        for i in range(w-1):
            m=tate[0][i][i][k]
            for j in range(i+1,w-1):
                if grid[k][j]!=grid[k][j-1]:
                    break
                m=min(tate[0][j][j][k],m)
                tate[0][i][j][k]=m
    
    
    #終わるまでやる
    #yoko= #複雑度、上、下、横
    #tate= #複雑度、左、右、縦
    for c in range(1,17):
        if yoko[c-1][0][h-1][0]==w:
            print(c)
            break
        for i in range(h):
            for j in range(i,h):
                for k in range(w):
                    temp=yoko[c-1][i][j][k]
                    if temp+k==w:
                        yoko[c][i][j][k]=max(temp,yoko[c][i][j][k])
                    else:
                        yoko[c][i][j][k]=max(temp+yoko[c-1][i][j][k+temp],yoko[c][i][j][k])
                    if j!=h-1:
                        temp2=tate[c-1][k][k+temp-1][j+1]
                        yoko[c][i][j+temp2-1][k]=max(temp,yoko[c][i][j+temp2-1][k])
        
        for i in range(w):
            for j in range(i,w):
                for k in range(h):
                    temp=tate[c-1][i][j][k]
                    if temp+k==h:
                        tate[c][i][j][k]=max(temp,tate[c][i][j][k])
                    else:
                        tate[c][i][j][k]=max(temp+tate[c-1][i][j][k+temp],tate[c][i][j][k])
                    if j!=w-1:
                        temp2=yoko[c-1][k][k+temp-1][j+1]
                        tate[c][i][j+temp2-1][k]=max(temp,tate[c][i][j+temp2-1][k])
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math
INF = float("inf")


def solve(H, W, A):
    x, y = set(), set()

    for i in range(H):
        for j in range(W):
            if j-1 >= 0:
                # print(A[i][j], A[i][j-1])
                if A[i][j] != A[i][j-1]:
                    x.add(j-1)
            if i-1 >= 0:
                if A[i][j] != A[i-1][j]:
                    y.add(i-1)
    # print(x)
    # print(y)
    b1 = math.ceil(math.log2(len(x)+1))
    b2 = math.ceil(math.log2(len(y)+1))
    print(b1+b2)


def main():
    H, W = map(int, input().split())
    A = []
    for i in range(H):
        A.append(input())

    solve(H, W, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def complexity(H: int, W: int, A: list)->int:
    if H == 1:
        # 1 行のものは、白ますの連続領域と黒ますの連続領域を
        # n 個とすると [n/2] が複雑さとなる。
        part = 1
        c = A[0][0]

        for a in A[0]:
            if a != c:
                part += 1
            c = a

        return part//2

    else:
        # 同じ行を圧縮する。
        complexities = []
        s = A[0]
        h = 0
        while h < H:
            s = A[h]
            while h+1 < H and s == A[h+1]:
                h += 1

            complexities.append(complexity(1, W, [s]))
            h += 1

        def sum_bin(l: int, r: int)->int:
            if l == r:
                return -1

            if l+1 == r:
                return complexities[l]

            return max(sum_bin(l, (l+r)//2), sum_bin((l+r)//2, r)) + 1

        return sum_bin(0, len(complexities))


if __name__ == "__main__":
    H = 0
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]

    ans = complexity(H, W, A)
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# agc033/agc033_d
import re
import math
import fractions
import numpy as np


[H, W] = [int(x) for x in input().split()]
A = np.zeros((H, W), dtype=np.int)
for i in range(H):
    input_str = input()
    for j in range(W):
        A[i][j] = int(input_str[j] == '#')
# #: 1, .: 0


def comp(c):
    if c.sum() == 0 or c.prod() == 1:
        return 1
    row = c.shape[0]
    col = c.shape[1]
    comps = [0] * (row + col - 2)
    for i in range(1, row):
        comps[i - 1] = max(comp(c[:i, :]), comp(c[i:, :]))
    for j in range(1, col):
        comps[row + j - 2] = max(comp(c[:, :j]), comp(c[:, :j]))
    return min(comps) + 1


print(comp(A))

Submission status: Wrong Answer

Solution code:
from math import ceil
from math import log2
H, W = map( int, input().split())
A = [ input() for _ in range(H)]
T = 0
i = 0
for i in range(H-1):
    if A[i] == A[i+1]:
        T += 1
S = 0
for i in range(W-1):
    check = 1
    for k in range(H):
        if A[k][i] != A[k][i+1]:
            check = 0
            break
    if check == 1:
        S += 1
if H-T == 1:
    print(ceil(log2(W-S)))
elif W-S == 1:
    print(ceil( log2(H-T)))
elif H-T == 2:
    print(2*ceil(log2(W-S)))
elif H-S == 2:
    print(ceil( log2(H-T))*2)
else:
    print( ceil( log2(H-T+1)-1)*ceil(log2(W-S+1)-1))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
f = [input() for _ in [0] * h]
rc = 0
for r1, r2 in zip(f, f[1:]):
    if r1 != r2:
        rc += 1
ft = list(map(''.join, zip(f)))
cc = 0
for r1, r2 in zip(ft, ft[1:]):
    if r1 != r2:
        cc += 1
ans = 0
while rc > 0 or cc > 0:
    if rc > cc:
        rc = rc // 2
    else:
        cc = cc // 2
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
from math import log2
H, W = map( int, input().split())
A = [ input() for _ in range(H)]
T = 0
i = 0
for i in range(H-1):
    if A[i] == A[i+1]:
        T += 1
S = 0
for i in range(W-1):
    check = 1
    for k in range(H):
        if A[k][i] != A[k][i+1]:
            check = 0
            break
    if check == 1:
        S += 1
if H-T == 1:
    print(ceil(log2(W-S)))
elif W-S == 1:
    print(ceil( log2(H-T)))
elif H-T == 2:
    print(2*ceil(log2(W-S)))
elif H-S == 2:
    print(ceil( log2(H-T))*2)
else:
    print( ceil( log2(H-T))*ceil(log2(W-S)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

H, W = map(int, input().split())

a = [input() for i in range(H)]

ans = 0

for l in a:
    count = 1
    ss = l[0]
    for s in l:
        if s != ss:
            count += 1
            ss = s
    if ans < count:
        ans = count
for i in range(W):
    count = 1
    ss = a[0][i]
    for j in range(H):
        if a[j][i] != ss:
            count += 1
            ss = a[j][i]
    if ans < count:
        ans = count
if ans == 1:
    ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

H, W = map(int, input().split())

a = [input() for i in range(H)]

ans = 0

for l in a:
    count = 1
    ss = l[0]
    for s in l:
        if s != ss:
            count += 1
            ss = s
    if ans < count:
        ans = count
for i in range(W):
    count = 1
    ss = a[0][i]
    for j in range(H):
        if a[j][i] != ss:
            count += 1
            ss = a[j][i]
    if ans < count:
        ans = count


print(ans)

Submission status: Wrong Answer

Solution code:
import math
HW=list(map(int, input().split()))
H=HW[0]
W=HW[1]

A=[0]*H
#行列のセット
for i in range(H):
  S = input()
  dmy = []
  for j in range(W):
    dmy.append(S[j])
  A[i]=dmy

#行の分割数
sep_h=1
for i in range(H-1):
  if A[i] != A[i+1]:sep_h+=1
#列の分割数
sep_w=1
for j in range(W-1):
  flg=False
  for i in range(H):
    if A[i][j] !=A [i][j+1]:
      flg=True
  if flg:sep_w+=1


comp=math.ceil(math.log2(sep_h))+math.ceil(math.log2(sep_w))
print(int(comp))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
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):
        for j in range(W):
            for ii in range(i, H):
                if X[i][j][ii] >= 0 and X[i][X[i][j][ii] + 1][ii] >= 0:
                    X[i][j][ii] = X[i][X[i][j][ii] + 1][ii]
            for jj in range(j, W):
                if Y[i][j][jj] >= 0 and Y[Y[i][j][jj] + 1][j][jj] >= 0:
                    Y[i][j][jj] = Y[Y[i][j][jj] + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Y[i][j][jj] < ii:
                    jj -= 1
                if jj >= j:
                    X[i][j][ii] = max(X[i][j][ii], jj)
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and X[i][j][ii] < jj:
                    ii -= 1
                if ii >= i:
                    Y[i][j][jj] = max(Y[i][j][jj], ii)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
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(17):
    if X[0][0][H-1] == W-1:
        print(k)
        exit()
    for i in range(H):
        for j in range(W):
            for ii in range(i, H):
                if X[i][j][ii] >= 0 and X[i][X[i][j][ii] + 1][ii] >= 0:
                    X[i][j][ii] = X[i][X[i][j][ii] + 1][ii]
            for jj in range(j, W):
                if Y[i][j][jj] >= 0 and Y[Y[i][j][jj] + 1][j][jj] >= 0:
                    Y[i][j][jj] = Y[Y[i][j][jj] + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Y[i][j][jj] < ii:
                    jj -= 1
                if jj >= j:
                    X[i][j][ii] = max(X[i][j][ii], jj)
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and X[i][j][ii] < jj:
                    ii -= 1
                if ii >= i:
                    Y[i][j][jj] = max(Y[i][j][jj], ii)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [[0] * (W + 1)] + [[0] + [0 if a == "." else 1 for a in input()] for _ in range(H)]
for i in range(H):
    for j in range(W+1):
        A[i+1][j] += A[i][j]
for i in range(H+1):
    for j in range(W):
        A[i][j+1] += A[i][j]
D = {}

def calc(i1, i2, j1, j2):
    d = (i1 << 24) ^ (i2 << 16) ^ (j1 << 8) ^ (j2)
    if d in D:
        return D[d]
    
    s = A[i2][j2] - A[i2][j1] - A[i1][j2] + A[i1][j1]
    if s == 0 or s == (i2 - i1) * (j2 - j1):
        D[d] = 0
        return 0
    re = 100
    if j2 - j1 > 1:
        l = j1
        r = j2
        while r - l > 1:
            m = (l + r) // 2
            c1 = calc(i1, i2, j1, m)
            c2 = calc(i1, i2, m, j2)
            re = min(re, max(c1, c2) + 1)
            if c1 == c2:
                break
            if c1 < c2:
                l = m
            else:
                r = m
    if i2 - i1 > 1:
        l = i1
        r = i2
        while r - l > 1:
            m = (l + r) // 2
            c1 = calc(i1, m, j1, j2)
            c2 = calc(m, i2, j1, j2)
            re = min(re, max(c1, c2) + 1)
            if c1 == c2:
                break
            if c1 < c2:
                l = m
            else:
                r = m
    D[d] = re
    return re

print(calc(0, H, 0, W))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [[0] * (W + 1)] + [[0] + [0 if a == "." else 1 for a in input()] for _ in range(H)]
for i in range(H):
    for j in range(W+1):
        A[i+1][j] += A[i][j]
for i in range(H+1):
    for j in range(W):
        A[i][j+1] += A[i][j]

def calc(i1, i2, j1, j2):
    s = A[i2][j2] - A[i2][j1] - A[i1][j2] + A[i1][j1]
    if s == 0 or s == (i2 - i1) * (j2 - j1):
        return 0
    re = 100
    if j2 - j1 > 1:
        l = j1
        r = j2
        while r - l > 1:
            m = (l + r) // 2
            c1 = calc(i1, i2, j1, m)
            c2 = calc(i1, i2, m, j2)
            re = min(re, max(c1, c2) + 1)
            if c1 == c2:
                break
            if c1 < c2:
                l = m
            else:
                r = m
    if i2 - i1 > 1:
        l = i1
        r = i2
        while r - l > 1:
            m = (l + r) // 2
            c1 = calc(i1, m, j1, j2)
            c2 = calc(m, i2, j1, j2)
            re = min(re, max(c1, c2) + 1)
            if c1 == c2:
                break
            if c1 < c2:
                l = m
            else:
                r = m
    return re

print(calc(0, H, 0, W))

Submission status: Time Limit Exceeded

Solution code:
import sys
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    H, W = MAP()
    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)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w=map(int,input().split())
    grid=[input() for _ in [0]*h]
    yoko=[[[0]*w for _ in [0]*h] for _ in [0]*h] #複雑度、上、下、横
    tate=[[[0]*h for _ in [0]*w] for _ in [0]*w] #複雑度、左、右、縦
    
    #初期化
    
    for i in range(h):
        cnt=2
        yoko[i][i][w-1]=1
        for j in range(w-2,-1,-1):
            if grid[i][j]==grid[i][j+1]:
                yoko[i][i][j]=cnt
                cnt+=1
            else:
                yoko[i][i][j]=1
                cnt=2
    for i in range(w):
        cnt=2
        tate[i][i][h-1]=1
        for j in range(h-2,-1,-1):
            if grid[j+1][i]==grid[j][i]:
                tate[i][i][j]=cnt
                cnt+=1
            else:
                tate[i][i][j]=1
                cnt=2
    
    for k in range(w):
        for i in range(h-1):
            m=yoko[i][i][k]
            for j in range(i+1,h):
                if grid[j][k]!=grid[j-1][k]:
                    break
                m=min(yoko[j][j][k],m)
                yoko[i][j][k]=m
    
    for k in range(h):
        for i in range(w-1):
            m=tate[i][i][k]
            for j in range(i+1,w):
                if grid[k][j]!=grid[k][j-1]:
                    break
                m=min(tate[j][j][k],m)
                tate[i][j][k]=m
    
    #終わるまでやる
    #yoko= #複雑度、上、下、横
    #tate= #複雑度、左、右、縦
    for c in range(1,18):
        if yoko[0][h-1][0]==w:
            print(c-1)
            break
        yoko2=[[[0]*w for _ in [0]*h] for _ in [0]*h] #複雑度、上、下、横
        tate2=[[[0]*h for _ in [0]*w] for _ in [0]*w] #複雑度、左、右、縦
        for i in range(h):
            for j in range(i,h):
                for k in range(w):
                    temp=yoko[i][j][k]
                    if temp+k==w:
                        yoko2[i][j][k]=temp
                    else:
                        yoko2[i][j][k]=max(temp+yoko[i][j][k+temp],yoko2[i][j][k])

        for i in range(h):
            for j in range(i,h):
                l=w-1
                for k in range(w-1,-1,-1):
                    while k<=l:
                        temp=tate[k][l][i]
                        if i+temp>j:
                            yoko2[i][j][k]=max(l-k+1,yoko2[i][j][k])
                            break
                        elif i+temp+tate[k][l][i+temp]>j:
                            yoko2[i][j][k]=max(l-k+1,yoko2[i][j][k])
                            break
                        else:
                            l-=1
        
        for i in range(w):
            for j in range(i,w):
                for k in range(h):
                    temp=tate[i][j][k]
                    if temp+k==h:
                        tate2[i][j][k]=temp
                    else:
                        tate2[i][j][k]=max(temp+tate[i][j][k+temp],tate2[i][j][k])       
                        
        for i in range(w):
            for j in range(i,w):
                l=h-1
                for k in range(h-1,-1,-1):
                    while k<=l:
                        temp=yoko[k][l][i]
                        if i+temp>j:
                            tate2[i][j][k]=max(l-k+1,tate2[i][j][k])
                            break
                        elif i+temp+yoko[k][l][i+temp]>j:
                            tate2[i][j][k]=max(l-k+1,tate2[i][j][k])
                            break
                        else:
                            l-=1
        
        yoko=yoko2
        tate=tate2
        
if __name__ == '__main__':
    main()