题解 | #矩阵中的路径#
矩阵中的路径
http://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
# 我对这题的想法是，将之前走过的路径用元组列表的方式进行存储
class Solution:
res = False
def hasPath(self, matrix: List[List[str]], word: str) -> bool:
# write code here
self.res = False
self.myBacktracking(matrix, [], word)
return self.res
def myBacktracking(self, matrix: List[List[str]], path: List, word: str):
# 1.回溯的终止条件，因为我加入了剪枝，因此只需要长度相符就可以
if self.res == True:
return
if path and len(path) == len(word):
temp = path[-1]
if word[-1] == matrix[temp[0]][temp[1]]:
self.res = True
return
# 2.1回溯的分支选择，初始为，起点任意，也要回溯
if len(path) == 0:
# path = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
path.append((i, j))
self.myBacktracking(matrix, path, word)
path.pop()
else:
# 3.剪枝，当前路径字符串已经不对，不需要往下走了
# 检查当前路径
for ind, val in enumerate(path):
pathchar = matrix[val[0]][val[1]]
if pathchar != word[ind]:
return
# 2.2分支选择path的最后一个元素代表上次走到哪里了，朝他的四周考虑
# 但如果四周某个元素已经在路径中则放弃选择
# 4.回溯，每个选择要撤回，再去做别的选择
i, j = path[-1]
# 上，右，下，左
if i - 1 >= 0 and (i - 1, j) not in path:
path.append((i - 1, j))
self.myBacktracking(matrix, path, word)
path.pop()
if j + 1 < len(matrix[0]) and (i, j + 1) not in path:
path.append((i, j + 1))
self.myBacktracking(matrix, path, word)
path.pop()
if i + 1 < len(matrix) and (i + 1, j) not in path:
path.append((i + 1, j))
self.myBacktracking(matrix, path, word)
path.pop()
if j - 1 >= 0 and (i, j - 1) not in path:
path.append((i, j - 1))
self.myBacktracking(matrix, path, word)
path.pop()
