Backjun-四叉木1992号

四叉木1992号

👏 キーポイント:代表的な分割征服問題。詳細は図で説明する。

このとき,xはw,bが混在している場合の表現である.(画像を説明するために提供されるため、コードはxを実現しない.)
分割征服とは何ですか.
再帰関数により数列を1の値に分割し,マージする過程である.そこで,再帰関数により最小の矩形に分割し,次の矩形(2 X 2)が白色であるか混合色であるかを決定した.このように(11)->(22)は,徐々に統合される過程を経る.詳しくはコードで説明します.

🎂 コード#コード#

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(str, input())))

def check(y0,x0,y1,x1,n):
    # 수열의 길이가 1일 경우 종료
    if n == 1:
        return graph[y0][x0]

    # 병합
    a = n // 2

    r1 = check(y0,x0,y1+a,x1+a,a) #왼쪽 위
    r2 = check(y0,x0+a,y1-a,x1,a) #오른쪽 위
    r3 = check(y0+a,x0,y1,x1-a,a) #왼쪽 아래
    r4 = check(y0+a,x0+a,x1,y1,a) #오른쪽 아래

    # 해당 트리의 가지들을 삭제시킨다. 
    if r1 == r2 == r3 == r4 and len(r1) == 1:
        
        return r1

    return "(" +r1+r2+r3+r4 + ")"

print(check(0,0,n,n,n))     

if=1、すなわち数列の長さが1になるまで、分割プロセスを行います.
分割プロセスは4つの部分に分けることができます.

4つの分割項目の長さがいずれも1であり、4つの項目の長さが同じである場合、代表値の1つであるr 1が返される.画像で表現するなら

すなわち、quad(,,,,n=2)の戻り値は(www)であるが、r 1=r 3=r 4=len(r 1)=1:構文により、同様の場合、戻り値を代表値wとして、以下の枝全てを削除することができる.