當前位置:成語大全網 - 新華字典 - DFS+回溯 搜索二維矩陣中相鄰元素的遞歸方法

DFS+回溯 搜索二維矩陣中相鄰元素的遞歸方法

請設計壹個函數,用來判斷在壹個矩陣中是否存在壹條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意壹格開始,每壹步可以在矩陣中向左、右、上、下移動壹格。如果壹條路徑經過了矩陣的某壹格,那麽該路徑不能再次進入該格子。例如,在下面的3×4的矩陣中包含壹條字符串“bfce”的路徑(路徑中的字母用加粗標出)。

[["a"," b ","c","e"],

["s"," f "," c ","s"],

["a","d"," e ","e"]]

但矩陣中不包含字符串“abfb”的路徑,因為字符串的第壹個字符b占據了矩陣中的第壹行第二個格子之後,路徑不能再次進入這個格子。

利用DFS+回溯遞歸的思想,其中這道題可以學習的是二維數組的相鄰元素搜索的方法:創建dir字典 巧用auto來完成每個相鄰元素的訪問