目錄
1. 問題描述
2. 解題分析
3. 代碼及測驗
4. 后記
1. 問題描述
2. 解題分析
似曾相似燕歸來，，，
第一感就認出了這道題目跟之前“Q32：榻榻米的鋪法”的相似之處，本題完全可以看作是Q32的增強版，在Q32中，榻榻米的尺寸是固定的1x2的大小，而本題可以看作是用任意尺寸長方形或正方形對房間鋪設的問題！
基于這一認識，可以直接基于Q32的題解進行一些適當修改就可以的得到本題的題解，喜歡挑戰的小伙伴如果沒有做過前面的Q32（或者做過了但是記憶模糊了）的話，可以先獨立做做這道題目，如果卡住了再回頭去看一下Q32的題解看看能不能得到啟發，最后還是卡住了的話，再看以下題解，
基于Q32的題解方案，有以下要點：
- 外加圍欄，以方便判斷
- 行掃描（或者列掃描也可以，道理相同），以很小的冗余掃描代價來換取巨大的判斷簡化的利益
- 從某一個點出發的可能的合并（對應于榻榻米鋪法）方法的遍歷，
第3點這是本題與Q32的本質的差異點，這里就不解釋了，直接看代碼很簡單明了，單就代碼而言甚至比Q32的還要簡單，
其中利用到了numpy.any()函式用于判斷某矩形區域內是否全0，因為本題中并沒有要求給出合并方案的圖示化（事實上也不可能，因為種類數之多遠遠超出了直感），所以在遞回呼叫時沒有給合并塊（“榻榻米”）編號并標記到格點內，而只是簡單地用“0”表示空格，“1”表示已經被合并的格子，
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Sat Oct 16 08:23:03 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
# from collections import deque
import itertools as it
import numpy as np
H = 4 # Height, vertical
W = 4 # Width, horizontal
# cells initialization, with a guard band surrounding the original cells
# The guard band is initialized to '-1' to simplify the judgement processing.
cells = np.zeros((H+2, W+2))
cells[0,:] = -1
cells[H+1,:] = -1
cells[:,0] = -1
cells[:,W+1] = -1
count = 0
def combine_cells(h,w)->int:
'''
Parameters
----------
(h,w) : The current exploration point.
h represents row index, w represents col index.
Returns: int
The number of total arrangement starting from the point (h,w), together
with the current cells status, which is a global variable
'''
global count
# print(h,w,idx)
if h == H + 1:
count = count + 1
# print(cells)
elif w == W + 1:
# Reach the right boundary, go to explore the next row from the left
combine_cells(h+1, 1)
elif cells[h,w] > 0:
# This grid has been occupied, move to the right one
combine_cells(h, w+1)
else:
for i in range(h,H+1):
for j in range(w,W+1):
# Judge whether (h,w)--(i,j) ractangulat can be combined.
# Here, (h,w) represents top-left corner, (i,j) represent right-down corner
if ~np.any(cells[h:i+1,w:j+1]):
cells[h:i+1,w:j+1] = 1
combine_cells(h, j+1)
cells[h:i+1,w:j+1] = 0
tStart = time.perf_counter()
combine_cells(1, 1)
tCost = time.perf_counter() - tStart
print('count = {0}, tCost = {1:6.3f}(sec)'.format(count,tCost)) 運行結果：count = 70878, tCost = 1.471(sec)
4. 后記
原書中給出了好幾頁的分析和題解，沒有耐心看（反正已經有了個解墊底^-^），而且可能也很難看懂，這種問題思路上沒有對上路的話，盡量別人blabla說一大堆估計也很難跟得上，相信很多小伙伴們都會有同感，
盡管這道題目在本書中是屬于高級篇，但是基于Q32我幾乎瞬間就得出的解決方案，由此也說明循序漸進的積累的重要性，
這個結果非常反直覺，小小的4*4的網格區間的單元合并居然能夠整出這么多種的可能性，真的是很神奇，
另外，本題還有個進一步的要求是，求最后不包含1x1尺寸格子（也就是不允許有未合并的單元格）的合并方案數，這個只需要在以上題解中稍作條件修改就可以得到，留給有興趣的小伙伴們自己嘗試，答案是1208種，
上一篇：Q55: 平分蛋糕
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/319656.html
標籤：其他
下一篇：回復程式猿的重啟人生