天天看點

算法學習之路|方格分割

6x6的方格,沿着格子的邊線剪開成兩部分。

要求這兩部分的形狀完全相同。

試計算:

包括這3種分法在内,一共有多少種不同的分割方法。

注意:旋轉對稱的屬于同一種分割法。

請送出該整數,不要填寫任何多餘的内容或說明文字。

解題思路:

首先建立一個模型:即從(3,3)開始一刀切,有多少種切法

應用算法:深度周遊/回溯

小技巧:

切痕為1,沒切的地方為0.

切過就無法再次切了,即遇到1回溯,遇到0就周遊。

當成蝸牛型環路的時候因為最後四個方向都是1,是以一直回溯到出環路,這個問題無需考慮.

繼續閱讀