1. 問題描述：
如下圖, 有12張連在一起的12生肖的郵票。現在你要從中剪下5張來，要求必須是連着的。（僅僅連接配接一個角不算相連）
比如，下面兩張圖中，粉紅色所示部分就是合格的剪取
請你計算，一共有多少種不同的剪取方法。
輸出
請填寫表示方案數目的整數。
2. 思路分析：
① 因為要求必須剪的五張郵票數連接配接在一起的，是以根據這個特點我們可以知道可以使用dfs搜尋進行五個方塊的連通，一開始的想法是從目前的位置(i，j)出發，其中i,j表示二維坐标對應的位置，從目前的位置出發開始dfs搜尋，每搜尋一個位置那麼就标記目前的(i， j)位置但是後面發現有的情況是漏掉了的，比如從第三行的數字9開始，因為之前已經搜尋過第一行與第二行了是以這個時候以9開頭的郵票是不能夠剪成功的（最多存在9,10,11,12四塊）而比如以9開始的1,2,3,5,9就是一個合法的剪法，是以上面這樣标記是會忽略一些情況的，是以每一次從起點開始dfs搜尋結束之後标記目前二維坐标位置已經通路是錯誤的解法
② 在網上看了一下具體的代碼，發現正确的解法是從12個數字中選擇出5個數字，然後記錄下選擇的5個數字，将5個數字映射到二維平面對應的坐标上，通過另外一個dfs2方法檢驗選擇的5個數字是否連通，思路其實還是很好了解的。總的來說是使用遞歸生成12選5的數字，可以使用遞歸的方法來生成12個數字選5個數字的組合方式，在生成5個數字的過程中需要使用一個清單記錄下這5個數字，并且将5個數字對應的坐标映射在二維平面上，然後再一次使用dfs檢查連通性，答案是116
3. 代碼如下：
組合 + 連通性判斷：
from typing import List
res = 0
# count用來記錄12選5個數字的下标
count = 0
# n表示
n = 0
A = [0] * 5
pos = [[0, 1], [0, -1], [-1, 0], [1, 0]]
# 檢驗5個數字在二維平面上的的連通性
def dfs2(x: int, y: int, B: List[List[int]]):
global n
for i in range(4):
x0, y0 = x + pos[i][0], y + pos[i][1]
if 0 <= x0 < 3 and 0 <= y0 < 4 and B[x0][y0] == 1:
B[x0][y0] = 0
n += 1
dfs2(x0, y0, B)
# 不知道為什麼回溯之後結果會不正确
# B[x0][y0] = 1
def dfs(index: int):
global count
if count == 5:
# print(A)
# 注意在這裡需要使用global來修改全局變量如果沒有使用這個關鍵字會導緻修改不了
global res, n
x, y = 0, 0
B = [[0] * 4 for i in range(3)]
for i in range(5):
x0, y0 = (A[i] - 1) // 4, (A[i] - 1) % 4
if i < 4:
# 标記矩陣中選擇5個數字的二維坐标
B[x0][y0] = 1
else:
# 從最後一個坐标開始搜尋
x, y = x0, y0
n = 1
dfs2(x, y, B)
# 一開始的計數為1
if n == 5:
res += 1
else:
for i in range(index + 1, 13):
A[count] = i
count += 1
dfs(i)
count -= 1
if __name__ == '__main__':
dfs(0)
print(res)
錯誤代碼：
from typing import List
res = 0
pos = [[0, 1], [0, -1], [1, 0], [-1, 0]]
# rec用來記錄中間的遞歸結果看輸出結果是否正确
def dfs(x: int, y: int, count: int, vis: List[List[int]], rec: List[List[int]]):
global res
if count == 4:
for i in range(len(rec)):
print(rec[i])
print()
res += 1
for i in range(4):
x0, y0 = x + pos[i][0], y + pos[i][1]
# 可以到達目前的位置
if 0 <= x0 < 3 and 0 <= y0 < 4 and vis[x0][y0] == 0:
rec[x0][y0] = 1
vis[x0][y0] = 1
dfs(x0, y0, count + 1, vis, rec)
# 回溯
rec[x0][y0] = 0
vis[x0][y0] = 0
if __name__ == '__main__':
vis = [[0] * 4 for i in range(3)]
rec = [[0] * 4 for i in range(3)]
for i in range(3):
for j in range(4):
rec[i][j] = 1
vis[i][j] = 1
dfs(i, j, 0, vis, rec)
# 标記已經通路過的位置這樣可以避免重複計算某些剪法
vis[i][j] = 1
rec[i][j] = 0
print(res)