目錄
1. 問題描述
2. 解題分析
2.1 如何判斷能否鋪
2.2 狀態表示和遍歷
2.3 圍欄
3. 代碼及測驗
4. 后記
1. 問題描述
考慮叫做“儀式鋪法”的榻榻米鋪法，這種鋪法可以使相鄰榻榻米之間的接縫不會形成十字，象征著吉祥，舉個例子，如果一個房間看作由縱3*橫4個正方形方格構成，鋪滿這個房間需要6張榻榻米（榻榻米的大小是統一的1*2的長方形），則鋪法如下所示（還有與這兩個成上下或左右對稱的圖案此處略去）：
圖1 (3,4)的房間的兩種鋪法
求用14張榻榻米鋪滿大小為4*7的房間的鋪法，
2. 解題分析
深度優先路徑遍歷問題，
這一類問題的難點主要體現在（具體問題的形式千差萬別）如何將問題轉換為易于遍歷搜索的問題表述形式，或者如何找到有效的遍歷方式（包括節點狀態表示，以及如何確定鄰節點或者說子節點），
2.1 如何判斷能否鋪
經過分析可以發現，構成非法鋪法的一個關鍵特征是在某一個點的周圍4個塊均屬于4塊不同的榻榻米，如下圖所示兩個都是NG的鋪法，
圖2 非法的鋪法例
那如何把這種約束條件轉化為容易判別的形式（換句話說人眼識別以上NG圖案很容易，如何讓計算機能做出判斷）呢？比如說，如下圖的狀態，現在要判斷帶問號“？”的格子是否可以鋪下一張榻榻米（無論是縱還是橫？）
圖3 “？”格子能夠鋪？
如前所述，非法的鋪法中是指在某個交點周圍的4個格子分屬于不同的榻榻米，所以在判斷“？”處是否能鋪，作為充要條件（這里先不考慮觸及邊界的情況）就是判斷“左上、上、左”這個三個格子是否不全部屬于不同的榻榻米，換言之，只要“左上、上”屬于同一榻榻米、或者“上、左”屬于同一榻榻米即表明當前格子可以鋪新的榻榻米（“左上、左”肯定分屬不同的榻榻米不必判斷），反之，如果“左上、上”屬于不同榻榻米、且“上、左”屬于不同榻榻米則表明當前格子肯定不能鋪，據此可以判斷，上圖中，左邊不能鋪，右邊可以鋪，
這也就自然地引出了給到當前狀態為止已經鋪好的榻榻米進行編號的考慮，以方便進行以上判斷，
2.2 狀態表示和遍歷
【有點復雜的想法】
以整個房間的鋪設狀態作為圖的節點，可以表示為H*W的矩陣（H為縱向高度，W為橫向寬度），矩陣元素取值{0：尚未覆寫；非零IDX：已經序號IDX的榻榻米被覆寫}，起始狀態（即深度優先搜索樹的根節點）為全0狀態，終止狀態為全非零狀態，這樣這個問題就轉變成在一張圖中搜索從某個節點（全‘0’狀態）出發，到達另一個節點（全非零狀態）的所有路徑的問題，
然后，鄰節點搜索可以這樣考慮，遍歷與移近覆寫的區域相鄰（有共同的邊）的格子，檢查從各鄰接格子是否能夠鋪設（因為是從左上往右下搜索的方式，針對每個格子只需要考慮向右鋪或向下鋪），這種方法的好處是遞回深度會小一些，但是已覆寫區域的鄰接格子的查詢似乎比較麻煩，
【逐行掃描】
原書中給出的解法（這道題原書給出的Javascript代碼比ruby容易理解些好歹看懂了）很巧妙（當然要自己先撞墻了然后再讀懂了才能體會其中妙處并感嘆我怎么沒想到），
簡單地逐行（當然逐列也可以）逐格掃描過去，碰到邊界就切換到下一行，碰到已經被覆寫的就跳過去，針對既非越界也沒有被覆寫的格子結合當前已經鋪就的狀態進行是否能鋪（參見上一節的描述）的判斷，加上“圍欄”技巧（參見下一節）以及給榻榻米編號的技巧，得到了一個非常簡潔的實作，
這一解法的缺點可能是遞回深度相對來說會比較大，當問題規模比較大的時候容易觸及遞回深度限制（有待確認）
以下為(H=3,W=4)的遞回搜索示意圖（沒有畫出圍欄，可以把格點坐標按照matlab-style的從1開始的方式理解；黑點表示當前探索的格子，旁邊(x,y,idx)對應的遞回呼叫的引數）
2.3 圍欄
如原書中所述，對于棋盤類問題，很多時候，在問題界定的范圍外側加上圍欄就可以簡化邊界條件的判定，在本題解中，在H*W格子矩陣外圍追加一圈格子，并全部賦值為“-1”，在代碼中雖然沒有顯式地（explicitly）用到“-1”的判斷，但是在“if room[h,w+1]==0:”和“if room[h+1,w]==0:”判斷中隱式地（implicitly）利用到了，因為追加了外圍的一層，所以不必擔心(w+1)和(h+1)越界而導致矩陣訪問出錯；另外，由于初始化為“-1”，所以在上述判斷不會被誤判為有效的可填的格子，
3. 代碼及測驗
以下代碼是參照原書的“逐行掃描”策略的解法，改為“逐列掃描”也可以，另外，也沒有特意地寫一個列印出鋪好的圖案的函式--相對來說是一個比較trivial的事情，從列印出來的table應該很容易描畫出鋪好的圖案來，
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 16 07:18:04 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 # Heigth of the room
W = 7 # Weigth of the room
# room initialization, with a guard band surrounding the original room
# The guard band is initialized to '-1' to simplify the judgement processing.
room = np.zeros((H+2, W+2))
room[0,:] = -1
room[H+1,:] = -1
room[:,0] = -1
room[:,W+1] = -1
count = 0
def setTatami_rowscan(h,w,idx)->int:
'''
Parameters
----------
(h,w) : The current exploration point. h represents row number, w represents col number.
idx : The identifier index of Tatami to be arranged.
Returns: int
The number of total arrangement from the input condition.
'''
global count
# print(h,w,idx)
if h == H + 1:
count = count + 1
print(room)
elif w == W + 1:
# Reach the right boundary, go to explore the next row from the left
setTatami_rowscan(h+1, 1, idx)
elif room[h,w] > 0:
# This grid has been occupied, move to the right one
setTatami_rowscan(h, w+1, idx)
elif room[h-1,w]==room[h-1,w-1] or room[h,w-1]==room[h-1,w-1]:
# if (the same IDX for up and left-up) or (the same IDX for left and left-up),
# Tatami arrangement is allowed.
if room[h,w+1]==0:
# Horizontal arrangement is allowed
room[h,w] = idx
room[h,w+1] = idx
setTatami_rowscan(h, w+2, idx+1)
room[h,w] = 0
room[h,w+1] = 0
if room[h+1,w]==0:
# Vertical arrangement is allowed
room[h,w] = idx
room[h+1,w] = idx
setTatami_rowscan(h, w+1, idx+1)
room[h,w] = 0
room[h+1,w] = 0
tStart = time.perf_counter()
setTatami_rowscan(1, 1, 1)
tCost = time.perf_counter() - tStart
print('count = {0}, tCost = {1:6.3f}(sec)'.format(count,tCost))
運行結果（H=4, W=7）:
4. 后記
后面要回頭再把第一種【有點復雜的想法】也實作一下，并比較一下前面的關于當前實作方式會導致更深的遞回深度的問題是否存在，
上一篇：Q31: 計算最短路徑
下一篇：Q33: 飛車與角行的棋步
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301229.html
標籤：其他