image.png
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
maze = [list(matrix[i*cols:i*cols+cols]) for i in range(rows)]
visited = [[0]*cols for i in range(rows)]
flag = 0
for i in range(rows):
for j in range(cols):
if self.search(maze, rows, cols, i, j, 0, path, visited):
flag = 1
break
if flag:
return True
else:
return False
def search(self, maze, rows, cols, row, col, cur, path, visited):
if cur == len(path):
return True
hasPathFlag = False
if row >= 0 and row < rows and col >= 0 and col < cols and maze[row][col] == path[cur] and visited[row][col] == 0:
visited[row][col] = 1
cur += 1
hasPathFlag = self.search(maze, rows, cols, row -1, col, cur, path, visited) or\
self.search(maze, rows, cols, row + 1, col, cur , path, visited) or\
self.search(maze, rows, cols, row , col-1, cur , path, visited) or\
self.search(maze, rows, cols, row , col+1, cur , path, visited)
if not hasPathFlag:
visited[row][col] = 0
cur -= 1
return hasPathFlag
