题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径。
[[“a”,“b”,“c”,“e”], [“s”,“f”,“c”,“s”], [“a”,“d”,“e”,“e”]]
示例1
输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true
示例2
输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false
思路
递归
list1 = [
['a', 'b', 'c', 'e'],
['s', 'f', 'c', 's'],
['a', 'd', 'e', 'e'],
]
str1 = "abcced"
str_list = list(str1)
list_tuple = []
status_list = []
def main():
m = len(list1)
n = len(list1[0])
for i in range(0, m):
for j in range(0, n):
if list1[i][j] == str_list[0]:
list_tuple.append((i, j))
for i in list_tuple:
status_list = [(i[0], i[1])]
solution(i[0], i[1], 1)
print("false")
def solution(m, n, num):
print(list1[m][n])
if num < len(str_list):
if m < len(list1)-1 and list1[m+1][n] == str_list[num] and (m+1, n) not in status_list:
status_list.append((m+1, n))
solution(m+1, n, num+1)
if n < len(list1[0])-1 and list1[m][n+1] == str_list[num] and (m, n+1) not in status_list:
status_list.append((m, n + 1))
solution(m, n + 1, num + 1)
if m > 0 and list1[m - 1][n] == str_list[num] and (m-1, n) not in status_list:
status_list.append((m - 1, n))
solution(m - 1, n, num + 1)
if n > 0 and list1[m][n - 1] == str_list[num] and (m, n-1) not in status_list:
status_list.append((m, n - 1))
solution(m, n - 1, num + 1)
else:
pass
else:
print("true")
exit()
if __name__ == "__main__":
main()
