矩陣中的路徑

---

請設計一個函數，用來判斷在一個矩陣中是否存在一條路徑包含的字符按訪問順序連在一起恰好為給定字符串。

路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。

如果一條路徑經過了矩陣中的某一個格子，則之后不能再次進入這個格子。

注意：

• 輸入的路徑字符串不為空；
• 所有出現的字符均為大寫英文字母；

數據范圍

矩陣中元素的總個數 [0,900]。

路徑字符串的總長度 [1,900]。

樣例

matrix=
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]
]str="BCCE" , return "true" str="ASAE" , return "false"

---

題解

核心思想：深度優先搜索（DFS）結合回溯。

1. 起點枚舉：
   遍歷矩陣中的每一個單元格 (i, j) 作為可能的路徑起點。
2. DFS遞歸搜索：
   從起點出發，依次匹配字符串的每個字符。具體步驟如下：
   • 終止條件：
     當前字符與目標字符不匹配，或已匹配完所有字符（u == str.size() - 1）。
   • 路徑探索：
     向四個方向（上、右、下、左）擴展路徑，并跳過越界或已訪問的單元格。
   • 回溯恢復現場：
     搜索結束后恢復當前單元格的原始字符，避免影響其他路徑的搜索。

時間復雜度分析

• 起點數量：矩陣共有 m×n 個單元格，其中 m 為行數，n 為列數。
• 路徑分支：
  每個字符匹配后，最多有 3 個新方向可選（不能走回頭路），字符串長度為 k。
• 總時間復雜度：
  O(m×n×3?)，其中 k 為字符串長度。

class Solution {
public:bool hasPath(vector<vector<char>>& matrix, string str) {// 遍歷所有可能的起點for (int i = 0; i < matrix.size(); i++) {for (int j = 0; j < matrix[i].size(); j++) {if (dfs(matrix, str, 0, i, j)) {return true;}}}return false;}bool dfs(vector<vector<char>>& matrix, string& str, int u, int x, int y) {// 當前字符不匹配，直接返回falseif (matrix[x][y] != str[u]) return false;// 已匹配所有字符，返回trueif (u == str.size() - 1) return true;// 定義四個方向：上、右、下、左int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// 保存當前字符并標記為已訪問char original = matrix[x][y];matrix[x][y] = '*'; // 使用特殊字符標記已訪問// 向四個方向遞歸搜索for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];// 檢查新坐標是否越界if (nx >= 0 && nx < matrix.size() && ny >= 0 && ny < matrix[nx].size()) {if (dfs(matrix, str, u + 1, nx, ny)) {return true; // 找到路徑，提前返回}}}// 回溯：恢復當前單元格的原始字符matrix[x][y] = original;return false;}
};

---

代碼解釋

1. 主函數 hasPath：
   • 遍歷矩陣的每個單元格 (i, j)，作為DFS的起點。
   • 若某一起點出發能找到完整路徑，立即返回 true。
2. 遞歸函數 dfs：
   • 參數說明：
     • u：當前需匹配的字符在字符串中的索引。
     • x, y：當前搜索的矩陣坐標。
   • 字符匹配檢查：
     若當前單元格字符與目標字符不匹配，直接返回 false。
   • 終止條件：
     若已匹配所有字符（u == str.size() - 1），返回 true。
   • 方向探索：
     使用方向數組生成四個相鄰坐標，過濾越界位置后遞歸搜索。
   • 回溯恢復現場：
     將標記為 * 的單元格恢復為原字符，確保后續路徑搜索不受影響。

關鍵細節

• 避免重復訪問：
  通過臨時修改當前單元格為特殊字符 *，確保同一路徑中不重復使用單元格。
• 剪枝優化：
  一旦某條路徑找到解，立即通過 return true 終止后續搜索，減少不必要的遞歸。