[剑指Offer]矩阵中的路径

题目描述

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

解题思路

采用回溯法来解题。额外生成一个布尔矩阵,用来存放该位置是否已经被遍历过。从矩阵的所有位置出发,判断该位置是否等于路径第一个字符,如果等于,则递归判断周围的四个位置,并把该位置的布尔矩阵值改为True,如果路径被递归完,则说明可以找到通路,否则返回False

代码

Python(2.7.3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
visited = [False] * rows * cols # 用来存放是否已经遍历过该位置
for i in range(rows):
for j in range(cols):
if matrix[i * cols + j] == path[0]:
if self.find(matrix, rows, cols, path[1:], visited, i, j):
return True
return False

def find(self, matrix, rows, cols, path, visited, i, j):
if not path:
return True
visited[i * cols + j] = True
if (i > 0 and matrix[(i - 1) * cols + j] == path[0] and not visited[(i - 1) * cols + j] and self.find(matrix, rows, cols, path[1:], visited, i - 1, j)) \
or (i + 1 < rows and matrix[(i + 1) * cols + j] == path[0] and not visited[(i + 1) * cols + j] and self.find(matrix, rows, cols, path[1:], visited, i + 1, j)) \
or (j > 0 and matrix[i * cols + j - 1] == path[0] and not visited[i * cols + j - 1] and self.find(matrix, rows, cols, path[1:], visited, i, j - 1)) \
or (j + 1 < cols and matrix[i * cols + j + 1] == path[0] and not visited[i * cols + j + 1] and self.find(matrix, rows, cols, path[1:], visited, i, j + 1)):
return True
visited[i * cols + j] = False # 若没找到通的路径,则仍然把是否遍历的矩阵对应值复原
return False

运行时间:23ms
占用内存:5752k

参考

https://www.nowcoder.com/profile/8630909/codeBookDetail?submissionId=12631533