1. 項目概述從一道國賽真題看DFS的實戰應用最近在復盤藍橋杯國賽的歷年真題發現“矩陣計數”這類題目出現的頻率相當高而且常常作為區分選手能力的關鍵題。它不像一些純模擬題那樣直接也不像動態規劃那樣有固定的套路模板更多是考察對搜索算法的深入理解和靈活應用能力。題目通常會給一個矩陣的規模比如 n x m以及一些限制條件比如矩陣中只能填0或1并且要求不存在某些特定的子矩陣模式例如2x2的子矩陣全為1然后問滿足條件的矩陣有多少種。這本質上是一個狀態空間搜索問題而深度優先搜索DFS正是解決這類問題的利器。我剛接觸這類題時第一反應是暴力枚舉——每個格子要么0要么1那直接2^(n*m)種可能全試一遍不就行了但稍微算一下就知道不可行一個5x5的矩陣就有2^25約3300萬種狀態更別說國賽常見的更大規模了。這就需要DFS結合剪枝技巧在搜索樹構建的早期就果斷砍掉大量不可能到達最終解的分支。這不僅僅是寫一個遞歸函數那么簡單它涉及到如何高效地表示狀態、如何設計搜索順序以減少冗余、以及如何挖掘題目條件設計出強有力的剪枝策略。接下來我就結合自己的解題經驗拆解一下這類問題的通用思路和幾個關鍵的實現技巧。2. 問題核心與DFS建模思路拆解2.1 問題本質與狀態定義“矩陣計數”問題的核心是統計滿足特定約束的所有可能矩陣的數量。約束條件千變萬化但最常見的兩類是局部形狀約束例如禁止出現任何2x2的子矩陣全部為1或全部為0。這是藍橋杯非常愛考的一類因為它能很好地引出“基于當前位置的可行性判斷”這一剪枝思想。行列統計約束例如每一行1的個數、每一列1的個數需要滿足某個條件。無論約束如何我們都可以將矩陣的填充過程看作在一個 n x m 的網格上進行DFS。每個格子是一個“搜索層”我們需要決定在這個格子填0還是填1。狀態如何表示最直接的想法是用一個二維數組matrix[n][m]來記錄當前填充的狀態-1表示未填充0或1表示已填充。DFS函數簽名可能像這樣dfs(row, col)表示當前要填充第row行、第col列的格子。搜索順序的設計這很重要。按行優先從左到右從上到下的順序進行填充是最自然、也是最有利于剪枝的。因為當我們填充到(row, col)時它左上方的所有格子都已經確定了我們可以利用這些已知信息來判斷當前選擇是否會導致后續無解。2.2 DFS遞歸框架的搭建一個清晰的遞歸框架是基礎。假設矩陣大小為n行m列我們從(0, 0)開始搜索。def dfs(pos): # pos 是當前要處理的格子編號 pos row * m col if pos n * m: # 所有格子都處理完了 if check_all(): # 檢查整個矩陣是否滿足最終約束 global count count 1 return row pos // m col pos % m # 嘗試在當前格子填 0 matrix[row][col] 0 if is_partial_valid(row, col): # 關鍵剪枝部分合法才繼續 dfs(pos 1) # 回溯 matrix[row][col] -1 # 嘗試在當前格子填 1 matrix[row][col] 1 if is_partial_valid(row, col): dfs(pos 1) # 回溯 matrix[row][col] -1這個框架很簡單但有兩個關鍵函數check_all(): 當矩陣填滿后進行全局的、徹底的約束檢查。它只在到達葉子節點時調用一次。is_partial_valid(row, col):這是剪枝的靈魂。它在每次做出選擇填0或1后立即調用判斷在當前這個部分填充的狀態下是否已經必然違反了題目約束。如果已經違反就沒必要繼續向下搜索了直接回溯。對于“禁止2x2全1”這種約束is_partial_valid的實現非常高效我們只需要檢查以當前新填充的格子(row, col)作為右下角的2x2子矩陣如果存在的話是否非法。因為當我們在填充(row, col)時它左上方的(row-1, col-1),(row-1, col),(row, col-1)這三個格子如果坐標合法的狀態是已知的。如果這三個格子都是1并且當前我們也填1那么這個2x2子矩陣就全為1了當前狀態就是非法的必須剪枝。def is_partial_valid(row, col): # 檢查以 (row, col) 為右下角的潛在2x2子矩陣 # 只需要檢查當前格子填1的情況因為填0不可能構成全1矩陣 if matrix[row][col] 1: # 檢查左上、上、左三個格子 if row 1 and col 1: if matrix[row-1][col-1] 1 and matrix[row-1][col] 1 and matrix[row][col-1] 1: return False # 發現非法2x2全1子矩陣 return True這個剪枝的威力巨大它能在搜索的早期就排除掉大量無效分支。實測下來沒有這個剪枝5x5的矩陣都跑得吃力加上之后10x10甚至更大規模的矩陣都有可能在一定時間內求解。3. 核心優化技巧與實戰細節3.1 狀態壓縮與記憶化搜索當矩陣規模增大或者約束條件更復雜時單純的DFS剪枝可能依然會超時。這時就需要更高級的優化。狀態壓縮是一個經典思路。對于按行優先搜索當我們處理到第i行第j列時哪些信息是對后續搜索有決定性影響的對于“禁止2x2全1”問題當前行i的填充狀態以及上一行i-1的填充狀態共同決定了下一行哪些位置不能填1否則會與上一行形成非法的2x2。我們可以用二進制位來壓縮一行的狀態。例如一個寬度為m的列每一列填1或0可以用一個m位的二進制數來表示第k位為1表示該列填1。這樣我們的DFS狀態就可以定義為dfs(i, prev_state, curr_state, col)表示i: 當前正在填充的行號。prev_state: 上一行i-1行的壓縮狀態。curr_state: 當前行i行已經填充到第col列時的狀態。col: 當前正在填充的列號。那么is_partial_valid檢查就變成了位運算當我們要在(i, col)位置填1時需要檢查prev_state的第col位、以及curr_state的第col-1位如果存在是否都是1。這比操作二維數組快得多。更進一步我們可以引入記憶化搜索Memoization。狀態(i, prev_state, col)可能被重復計算多次。如果我們用DP的思想把dfs(i, prev_state, col)定義為“從第i行、第col列開始在上一行狀態為prev_state的約束下能填出多少種合法的剩余矩陣”那么就可以把結果緩存起來。當再次遇到相同的(i, prev_state, col)時直接返回緩存結果避免重復搜索子樹。from functools import lru_cache lru_cache(maxsizeNone) def dfs(row, prev_state, col): if col m: # 當前行填完進入下一行 return dfs(row 1, curr_state, 0) if row n: # 所有行都填完找到一種合法方案 return 1 total 0 # 嘗試填0 total dfs(row, prev_state, col 1) # 嘗試填1需要檢查是否與上一行形成非法2x2 # 檢查條件不能同時滿足 (prev_state在col位為1) 且 (col0時curr_state在col-1位為1) 且 (prev_state在col-1位為1) # 這里curr_state是當前行已填充的狀態我們需要在遞歸調用前判斷 # 更常見的寫法是在決定填1時構造新的new_curr_state然后判斷(new_curr_state, prev_state)是否合法 # 判斷函數 is_valid_transition(prev_state, new_curr_state) new_curr_state curr_state | (1 col) if is_valid_transition(prev_state, new_curr_state): total dfs(row, new_curr_state, col 1) return total這種“DFS狀態壓縮記憶化”的組合拳能將指數級復雜度的搜索問題轉化為狀態數可控的動態規劃問題。狀態數大約是n * (2^m) * m當m較小時比如 m10這個方法是完全可行的。這也是國賽題常見的套路考察選手能否將搜索問題轉化為狀壓DP。3.2 搜索順序與對稱性剪枝除了基于約束的剪枝利用問題的對稱性也能大幅減少搜索量。在很多矩陣計數問題中矩陣是方陣nm或者問題本身具有旋轉、翻轉對稱性。這些對稱的方案在本質上被視為同一種但我們的DFS會每一種都枚舉出來導致重復計數。例如一個關于中心點旋轉90度后相同的矩陣我們只應計數一次。一種處理方法是在搜索過程中加入規范化Canonical表示?；舅悸肥菍τ诿總€填充到一半或完整的矩陣我們計算出它所有對稱變換下的“最小”或“標準”表示比如轉化為字符串后取字典序最小的。在搜索過程中如果發現當前部分填充的狀態其規范表示不等于它自身說明它可以通過對稱性由“更小”的狀態得到那么當前分支就可以剪掉因為最終它會被那個“更小”的狀態搜索到并計數。實現對稱性剪枝通常比較復雜需要仔細處理部分填充狀態下的判斷。在競賽時間有限的情況下一個更實用的策略是先不考慮對稱性用DFS算出總數量包含重復如果題目要求的是“本質不同”的數量再根據對稱群的規模如正方形旋轉有4種加上翻轉可能8種去除以相應的數。但要注意這種方法的前提是所有方案都恰好被每個對稱操作映射到不同的方案即沒有“自對稱”的方案。如果存在自對稱的矩陣比如全0矩陣它不會被重復計數那么多次直接除法會導致錯誤。這時就需要用到Burnside引理或Polya計數定理來準確計算這就涉及到更深的組合數學知識了在國賽中出現屬于壓軸難度。3.3 邊界處理與代碼魯棒性在實現DFS時邊界條件的處理是bug的高發區。數組越界在is_partial_valid函數中檢查(row-1, col-1)等格子時務必先判斷row1和col1。我早期經常在這里寫出if matrix[row-1][col-1]...而忘記檢查下標導致程序在搜索第一行或第一列時崩潰。狀態回溯這是DFS的基石必須成對出現。我習慣采用“做出選擇-遞歸-撤銷選擇”的模式如上文代碼所示。在Python中對于整數等不可變對象在參數傳遞時是值傳遞天然具有回溯效果。但對于列表、字典等可變對象或者在C中使用全局數組就必須手動回溯。一個常見的錯誤是忘記在遞歸返回后撤銷選擇導致狀態污染。遞歸深度Python的默認遞歸深度限制通常1000對于 n*m 較大的矩陣可能不夠。例如一個30x30的網格遞歸深度就達到900。你需要使用sys.setrecursionlimit(1000000)來提高限制。但更根本的方法是評估問題規模如果實在太大可能就需要用迭代加深搜索IDS或者更高級的算法了。4. 從DFS到動態規劃的思維跨越對于“矩陣計數”這類問題DFS是直觀的起點但高效的解法往往最終落腳在動態規劃DP特別是狀壓DP。我們可以把DFS的記憶化搜索過程明確地寫成DP遞推式。定義dp[i][state]表示已經填充完前i行并且第i行的填充狀態為state二進制壓縮時合法的方案數。 那么狀態轉移方程為dp[i][curr_state] sum(dp[i-1][prev_state] for prev_state in all_states if is_valid_transition(prev_state, curr_state))其中is_valid_transition(prev_state, curr_state)函數判斷從上一行狀態prev_state到當前行狀態curr_state是否合法。對于“禁止2x2全1”的約束這個判斷就是對于任意相鄰兩列j和j1不能出現prev_state的第j位、第j1位以及curr_state的第j位、第j1位同時為1。這同樣可以用位運算快速判斷。def is_valid_transition(prev, curr): # 假設矩陣寬度為m # 檢查是否存在連續的列j使得 prev和curr在這些列上都是1 # 即 (prev curr) 的任意連續兩位不能都為1 combined prev curr # 檢查combined中是否有連續的1 # 方法將combined與自身左移一位進行與操作結果不為0則說明有連續1 return (combined (combined 1)) 0初始化dp[0][0] 1第0行可以認為是全0的空行只有1種狀態。最終答案就是sum(dp[n][state] for state in all_states)。這種DP方法的時間復雜度是O(n * (2^m) * (2^m))因為對于每個dp[i][curr]我們需要遍歷所有可能的prev。當m較大時比如15狀態數2^1532768兩兩判斷的復雜度是1e9級別依然會超時。這時需要進一步優化例如預處理出每個狀態所有合法的“下一行狀態”列表避免內層循環遍歷所有狀態。5. 實戰案例分析與調試心得5.1 案例藍橋杯典型題“方格計數”變種假設題目是在 n x m 的矩陣中填0/1要求不存在任何2x2的子矩陣全為1。求方案數。n, m 10。思路選擇n和m都不大但最大10x10狀態空間2^100巨大必須剪枝。由于約束是局部的2x2按行優先DFS配合“右下角檢查”剪枝是可行的。但為了更優可以采用狀壓DP。DP實現關鍵點狀態表示dp[row][state]state是當前行的二進制壓縮。合法性檢查行內合法性state本身不能有連續的1因為如果一行內有兩個連續的1并且上一行對應位置也是1就會形成2x2。所以合法的state需要滿足(state (state 1)) 0。行間合法性對于上一行狀態prev和當前行狀態curr需要滿足(prev curr) ((prev curr) 1) 0。即兩行按位與的結果不能有連續的1。初始化dp[0][0] 1。注意第0行是虛擬行狀態0代表全0。結果sum(dp[n][state])其中state是任意合法狀態。def solve(n, m): all_states [] # 預處理所有行內合法的狀態 for s in range(1 m): if s (s 1) 0: # 沒有連續的1 all_states.append(s) # 預處理狀態轉移關系from_state - [to_state_list] transition {s: [] for s in all_states} for s1 in all_states: for s2 in all_states: if (s1 s2) ((s1 s2) 1) 0: transition[s1].append(s2) dp [ [0] * (1 m) for _ in range(n1) ] dp[0][0] 1 # 虛擬第0行狀態為0 for i in range(1, n1): for prev in all_states: if dp[i-1][prev] 0: continue for curr in transition[prev]: dp[i][curr] dp[i-1][prev] ans sum(dp[n][s] for s in all_states) return ans5.2 調試與驗證技巧從小規模驗證永遠從最小的數據開始測試。比如 n1, m1答案應該是2[0], [1]。n2, m2手動枚舉所有16種矩陣排除掉包含2x2全1的其實只有一種全1矩陣答案應該是15。用你的程序跑一下看結果是否匹配。輸出中間狀態在DFS中可以打印出搜索到某個深度時的矩陣狀態或者DP中每行的方案數看看是否符合預期。對于DP計算完dp[1]即第一行后dp[1][state]應該等于行內合法的、狀態為state的方案數這很容易驗證。對拍寫一個暴力枚舉程序僅適用于非常小的n和m比如n,m4用它來生成小數據下的正確答案。然后用你的優化算法去跑同樣的數據對比結果是否一致。這是檢驗算法正確性最可靠的方法之一。時間復雜度估算在提交前估算最壞情況下的操作次數。例如上述DP解法預處理transition是 O( (2^m)^2 )主循環是 O(n * (2^m) * avg_transition)。當 m10時2^m1024平方約1e6主循環假設平均轉移數100n10則約1e6次操作完全在1秒內。做到心中有數避免盲目提交導致超時。5.3 常見“坑點”實錄整數溢出方案數可能非常大遠超int范圍。在C中要使用long long在Python中雖然整數不限但也要注意。藍橋杯的題目有時會要求取模一定要看清楚題目要求在每次加法或乘法后及時取模。初始化錯誤DP中dp[0][0]1是常見的初始化。但有些題目中第一行可能有特殊限制比如第一行不能全0那么初始化就需要改變。務必結合題意理解“第0行”這個虛擬狀態的含義。位運算優先級和的優先級問題。if s (s 1) 0:在Python中是錯誤的因為優先級高于。必須寫成if (s (s 1)) 0:。這是我早期常犯的錯誤調試起來很痛苦因為邏輯上看不出問題。狀態表示歧義用二進制位表示一行狀態時第0位是最低位代表最右邊的列還是最高位代表最左邊的列這需要統一。我習慣讓state的第j位對應第j列從0開始。在檢查連續列時左移操作 1就對應檢查相鄰的下一列列號1。只要在整個程序中保持一致即可。6. 性能瓶頸分析與進階策略當 n 和 m 繼續增大比如到15以上無論是DFS剪枝還是標準的狀壓DP都可能面臨性能壓力。這時需要思考更精妙的優化。1. 滾動數組優化DP數組dp[i][state]只依賴于dp[i-1][state]所以可以只用兩個一維數組dp_curr和dp_prev交替使用將空間復雜度從 O(n * 2^m) 降到 O(2^m)。2. 矩陣快速冪優化如果題目中的約束是“行間無關”的即下一行的合法狀態只依賴于上一行的狀態并且這個轉移關系對于每一行都是相同的就像我們上面討論的“禁止2x2全1”那么整個填充過程可以看作一個狀態轉移矩陣的連乘。定義矩陣M其大小是S x SS是合法狀態數M[prev][curr] 1當且僅當從狀態prev轉移到curr是合法的。那么從第0行虛擬行狀態0到第n行的方案數就是向量[1, 0, 0, ...]只有狀態0為1乘以矩陣M^n后所有元素的和。計算M^n可以使用矩陣快速冪時間復雜度為 O(S^3 * log n)。當合法狀態數 S 不大比如幾百而 n 非常大比如10^9時這種方法極其高效。這通常出現在“鋪瓷磚”一類的問題中。3. 輪廓線DP插頭DP對于更復雜的連通性約束比如要求所有1的格子構成一條路徑或者要求1的連通塊數量等狀壓DP每一行記錄一個狀態就不夠了需要記錄當前處理格子所在“輪廓線”上的更細致狀態。這是競賽中的高級話題難度很大但也是解決復雜矩陣計數問題的終極武器之一。它本質上是將狀態壓縮與DP結合到了極致按格遞推狀態表示當前已經處理過的格子和未處理格子之間的“分界線”上的情況。面對國賽級別的矩陣計數題我的策略通常是先嘗試最直觀的DFS剪枝寫一個暴力版本用于驗證小數據思路。然后分析約束的局部性嘗試轉化為狀壓DP。如果數據范圍暗示 n 大 m 小就采用標準狀壓DP如果 m 也偏大就要考慮是否有特殊的性質可以簡化狀態比如利用對稱性減少狀態數或者是否需要用到輪廓線DP。平時多積累不同約束對應的狀態表示和轉移方法比賽時才能快速識別并套用。