题解 | #矩阵中的路径#

矩阵中的路径

http://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6

关于回溯算法：

回溯算法的一个核心就是递归函数嵌套选择条件的循环。简单来说就是递归函数就是推进器，循环就是选择器

回溯算法的一个目标

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

本题的python解法，写得比较臃肿，懒得优化了。核心思想

1.最外层函数去找起始点并复制棋盘

2.内层函数通过get_next_index寻找下一步的选择列表，backtrack做推进器

3.推进器函数前置一堆终止判断

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
import copy
class Solution:
    def hasPath(self , matrix , word ):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == word[0]:
                    vis = copy.deepcopy(matrix)
                    if self.backtrack(word, i, j, 0, vis):
                        return True
        return False
 
    def backtrack(self, word, i, j, index, matrix):
        #print(index)
        if index == len(word)-1:
            return True
        if matrix[i][j] == True:
            return False
        #if index <= len(word)-2:
        index += 1
        choice_list = self.get_next_indexs(i, j, word[index], matrix)
        print(choice_list)
        if not choice_list:
            #matrix[i][j] = True
            return False
        if index == len(word)-1 and choice_list:
            return True
        for index_box in choice_list:
            ii = index_box[0]
            jj = index_box[1]
            matrix[i][j] = True
            if self.backtrack(word, ii, jj, index, matrix):
                return True
        return False
 
    def get_next_indexs(self, i, j, ch, matrix):
        res = []
        print(ch)
        #if ch == 'B':
        print(i, j, ch, matrix)
        #print(j)
        if i !=0 and matrix[i-1][j] == ch:
            res.append([i-1, j])
        if i < len(matrix)-1 and matrix[i+1][j] == ch:
            res.append([i+1, j])
        if j !=0 and matrix[i][j-1] == ch:
            res.append([i, j-1])
        if j < len(matrix[0])-1 and matrix[i][j+1] == ch:
            res.append([i, j+1])
        if ch == 'B':
            print(res)
        return res