Skip to content

Instantly share code, notes, and snippets.

@c02y
Created January 14, 2020 06:57
Show Gist options
  • Save c02y/31d3fe26a9e173f824c725220c2cb25b to your computer and use it in GitHub Desktop.
Save c02y/31d3fe26a9e173f824c725220c2cb25b to your computer and use it in GitHub Desktop.
12. 矩阵中的路径 回溯法(backtracking)
#!/usr/bin/env python3
# https://cyc2018.github.io/CS-Notes/#/notes/12.%20%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84
# https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc?f=discussion
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if not matrix:
return False
if not path:
return True
x = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]
for i in range(rows):
for j in range(cols):
if self.exist_helper(x, i, j, path):
return True
return False
def exist_helper(self, matrix, i, j, p):
if matrix[i][j] == p[0]:
if not p[1:]:
return True
matrix[i][j] = '' # NOTE:
if i > 0 and self.exist_helper(matrix, i-1, j, p[1:]):
return True
if i < len(matrix)-1 and self.exist_helper(matrix, i+1, j ,p[1:]):
return True
if j > 0 and self.exist_helper(matrix, i, j-1, p[1:]):
return True
if j < len(matrix[0])-1 and self.exist_helper(matrix, i, j+1, p[1:]):
return True
matrix[i][j] = p[0] # NOTE:
return False
else:
return False
def main():
# path = ['b', 'c', 'c', 'c', 'e', 'd']
path = ['b', 'c', 'c', 'e', 'd']
matrix = ['a', 'b', 'c', 'e',
's', 'f', 'c', 's',
'a', 'd', 'e', 'e']
rows = 3
cols = 4
result = Solution()
if result.hasPath(matrix, rows, cols, path):
print(str(path) + " has path!")
else:
print(str(path) + " no path!")
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment