[编程题]矩阵中的路径
- 热度指数：436950 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
示例1
输入
"ABCESFCSADEE",3,4,"ABCCED"
输出
true
示例2
输入
"ABCESFCSADEE",3,4,"ABCB"
输出
false
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
m = [[0 for j in range(cols)] for i in range(rows)]
for i in range(rows):
for j in range(cols):
m[i][j] = matrix[i*cols + j]
for i in range(rows):
for j in range(cols):
if m[i][j] == path[0]:
visited = [[i,j]]
if self.findpath(i, j,path[1:],m,visited,rows,cols):
return True
return False
def findpath(self, i, j, path, m, visited, rows, cols):
if i<0 or j<0 or i>=rows or j>=cols:
return False
if not path:
return True
if i-1 >= 0 and [i-1,j] not in visited and m[i-1][j] == path[0]:
visited.append([i-1,j])
if self.findpath(i-1, j,path[1:],m,visited,rows,cols):
return True
if j-1 >= 0 and [i,j-1] not in visited and m[i][j-1] == path[0]:
visited.append([i,j-1])
if self.findpath(i, j-1,path[1:],m,visited,rows,cols):
return True
if i+1 < rows and [i+1,j] not in visited and m[i+1][j] == path[0]:
visited.append([i+1,j])
if self.findpath(i+1, j,path[1:],m,visited,rows,cols):
return True
if j+1 < cols and [i,j+1] not in visited and m[i][j+1] == path[0]:
visited.append([i,j+1])
if self.findpath(i, j+1,path[1:],m,visited,rows,cols):
return True
else:
return False
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
m = [[0 for j in range(cols)] for i in range(rows)]
for i in range(rows):
for j in range(cols):
m[i][j] = matrix[i*cols + j]
for i in range(rows):
for j in range(cols):
if m[i][j] == path[0]:
visited = [[i,j]]
if self.findpath(i, j,path[1:],m,visited,rows,cols):
return True
return False
def findpath(self, i, j, path, m, visited, rows, cols):
if i<0 or j<0 or i>=rows or j>=cols:
return False
if not path:
return True
if i-1 >= 0 and [i-1,j] not in visited and m[i-1][j] == path[0]:
visited.append([i-1,j])
if self.findpath(i-1, j,path[1:],m,visited,rows,cols):
return True
if j-1 >= 0 and [i,j-1] not in visited and m[i][j-1] == path[0]:
visited.append([i,j-1])
if self.findpath(i, j-1,path[1:],m,visited,rows,cols):
return True
if i+1 < rows and [i+1,j] not in visited and m[i+1][j] == path[0]:
visited.append([i+1,j])
if self.findpath(i+1, j,path[1:],m,visited,rows,cols):
return True
if j+1 < cols and [i,j+1] not in visited and m[i][j+1] == path[0]:
visited.append([i,j+1])
if self.findpath(i, j+1,path[1:],m,visited,rows,cols):
return True
else:
return False
发表于 2021-02-01 03:37:37
回复(0)
python 回溯 ，这边转换成二维数组来计算
# -*- coding:utf-8 -*- class Solution: def hasPath(self, matrix, rows, cols, path): for k, v in enumerate(matrix): if v == path[0]: row, col = k // cols, k % cols xx = self.cover(matrix, cols) # TODO 二维数组的巨坑，任何赋值都是引用，每次都重新生成数组 if self.path(xx, row, col, path): return True return False # write code here def path(self, xx, rows, cols, value): try: if not value: return True if xx[rows][cols] == value[0]: xx[rows][cols] = "null" # 不能往回走 value = value[1:] return self.path(xx, rows + 1, cols, value)&nbs***bsp;self.path(xx, rows, cols + 1, value)&nbs***bsp;self.path(xx, rows - 1, cols, value)&nbs***bsp;self.path( xx, rows, cols - 1, value) except: return False def cover(self, matrix, cols): ll = [] for i in range(0, len(matrix), cols): l = [] for j in matrix[i:i + cols]: l.append(j) ll.append(l) return ll
发表于 2020-09-08 17:31:00
回复(0)
class Solution: def hasPath(self, matrix, rows, cols, path): self.flag_ = False if not matrix: return False if not path: return True matrix = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)] for row in range(rows): for col in range(cols): if matrix[row][col] == path[0]: self.mat = [[0 for j in range(cols)] for i in range(rows)] self.dfs(matrix,row,col, rows, cols, path) if self.flag_: return self.flag_ return self.flag_ def dfs(self, matrix,row,col, rows, cols, path): if not path: self.flag_ = True return if row >= rows&nbs***bsp;col >= cols&nbs***bsp;row < 0&nbs***bsp;col < 0: return if matrix[row][col] != path[0]: return if self.mat[row][col] == -1: return self.mat[row][col] = -1 self.dfs(matrix, row, col+1, rows, cols, path[1:]) self.dfs(matrix, row+1, col, rows, cols, path[1:]) self.dfs(matrix, row, col-1, rows, cols, path[1:]) self.dfs(matrix, row-1, col, rows, cols, path[1:]) return
发表于 2020-07-20 16:05:07
回复(0)
#新手代码，时间复杂度是O(cols*rows).
(2614)#踩坑：代码无法识别多条路径，例如输入参数[1,2,3,4,4,3,2,1],2,4,[1,2,3,4],尽管输出参数是True，但是#assistMatrix中只有一条路径。
class Solution:
def hasPath(self, matrix, rows, cols, path):
assistMatrix = [True]*rows*cols
for i in range(rows):
for j in range(cols):
if(self.hasPathAtAStartPoint(matrix,rows,cols, i, j, path, assistMatrix)):
return True
return False
def hasPathAtAStartPoint(self, matrix, rows, cols, i, j, path, assistMatrix):
if not path:
return True
index = i*cols+j
if i<0 or i>=rows or j<0 or j>=cols or matrix[index]!=path[0] or assistMatrix[index]==False:
return False
assistMatrix[index] = False
if(self.hasPathAtAStartPoint(matrix,rows,cols,i+1,j,path[1:],assistMatrix) or self.hasPathAtAStartPoint(matrix,rows,cols,i-1,j,path[1:],assistMatrix) or self.hasPathAtAStartPoint(matrix,rows,cols,i,j-1,path[1:],assistMatrix) or self.hasPathAtAStartPoint(matrix,rows,cols,i,j+1,path[1:],assistMatrix)):
return True
assistMatrix[index] = True
return False
def hasPath(self, matrix, rows, cols, path):
assistMatrix = [True]*rows*cols
for i in range(rows):
for j in range(cols):
if(self.hasPathAtAStartPoint(matrix,rows,cols, i, j, path, assistMatrix)):
return True
return False
def hasPathAtAStartPoint(self, matrix, rows, cols, i, j, path, assistMatrix):
if not path:
return True
index = i*cols+j
if i<0 or i>=rows or j<0 or j>=cols or matrix[index]!=path[0] or assistMatrix[index]==False:
return False
assistMatrix[index] = False
if(self.hasPathAtAStartPoint(matrix,rows,cols,i+1,j,path[1:],assistMatrix) or self.hasPathAtAStartPoint(matrix,rows,cols,i-1,j,path[1:],assistMatrix) or self.hasPathAtAStartPoint(matrix,rows,cols,i,j-1,path[1:],assistMatrix) or self.hasPathAtAStartPoint(matrix,rows,cols,i,j+1,path[1:],assistMatrix)):
return True
assistMatrix[index] = True
return False
发表于 2020-03-16 14:15:37
回复(0)
递归方法，这里没有用到回溯的思想，将字符串变成矩阵之后，如果经过一个点，就把它变成“0”（这里有点投机取巧了）
# -*- coding:utf-8 -*- class Solution: def hasPath(self, matrix, rows, cols, path): (1926)# write code here def backtrack(matrix,i,j,path): if i < 0&nbs***bsp;j < 0: return False if i >= rows&nbs***bsp;j >= cols: return False if matrix[i][j] == path[0] and len(path) == 1: return True elif matrix[i][j] == path[0] and len(path) > 1: t = list(matrix[i]) t[j] = "0" matrix[i] = ''.join(t) a=backtrack(matrix,i+1,j,path[1:]) b=backtrack(matrix, i, j+1, path[1:]) c=backtrack(matrix, i - 1, j, path[1:]) d=backtrack(matrix, i, j - 1, path[1:]) if a&nbs***bsp;b&nbs***bsp;c&nbs***bsp;d: return True else: return False tmp = [] while matrix: tmp.append(matrix[:cols]) matrix =matrix[cols:] for i in range(rows): for j in range(cols): if tmp[i][j] == path[0]: s = tmp[:] a = backtrack(s,i,j,path) if not a: continue else: return True return False
发表于 2020-03-09 16:38:28
回复(0)
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if matrix==None&nbs***bsp;rows<1&nbs***bsp;cols<1&nbs***bsp;path==None:
return False
#用来判定该格子是否已经访问过了
visited=[0 for i in range(rows*cols)]
pathlength=0
for x in range(rows):
for y in range(cols):
#此处是用于找到最开始的起点
if self.haspathcore(matrix,rows,cols,x,y,path,pathlength,visited):
return True
return False
def haspathcore(self,matrix,rows,cols,row,col,path,pathlength,visited):
if pathlength>=len(path):
#字符序列中字符都已匹配完成
return True
haspath=False
if row>=0 and row<rows and col>=0 and col<cols and matrix[row*cols+col]==path[pathlength] and not visited[row*cols+col]:
#当字符串匹配时就去找寻下一个格子的位置，有四种情况，只要有一种符合就够了
pathlength+=1
visited[row*cols+col]=1
haspath=self.haspathcore(matrix,rows,cols,row,col-1,path,pathlength,visited) \
&nbs***bsp;self.haspathcore(matrix,rows,cols,row,col+1,path,pathlength,visited) \
&nbs***bsp;self.haspathcore(matrix,rows,cols,row-1,col,path,pathlength,visited) \
&nbs***bsp;self.haspathcore(matrix,rows,cols,row+1,col,path,pathlength,visited)
if not haspath:
#如果往四个方向都没有匹配到下一个字符，则进行回溯
pathlength-=1
visited[row*cols+col]=0
return haspath 首先我们需要找到初始格子，然后就是从初始格子出发，当前格子与字符序列当前位置如果匹配的话，就寻找下一个格子，下一个格子是从四个方向上进行寻找。如果都没有找到就利用回溯的方法。回溯是在判定四个方向都无匹配的字符时才进行回溯。以此直到结束。
发表于 2020-02-16 23:20:56
回复(0)
Python非递归回溯。用栈记录经过的路径以及该路径点的下一步的方向，以0,1,2,3分别表示上右下左四个方向。
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if not matrix:
return False
entry = [i for i, v in enumerate(matrix) if v == path[0]]
for e in entry:
stack = [(e, -1)]
past = [e]
k = 1
while stack and k < len(path):
tar = path[k]
pos, direct = stack.pop()
d = direct + 1
while d < 4:
if (d == 0 and pos//cols >= 1 and pos-cols not in past and matrix[pos-cols] == tar) \
&nbs***bsp;(d == 1 and pos%cols <= cols-2 and pos+1 not in past and matrix[pos+1] == tar) \
&nbs***bsp;(d == 2 and pos//cols <= rows-2 and pos+cols not in past and matrix[pos+cols] == tar) \
&nbs***bsp;(d == 3 and pos%cols >= 1 and pos-1 not in past and matrix[pos-1] == tar):
break
d += 1
if d < 4:
new_pos = {0: pos-cols, 1: pos+1, 2: pos+cols, 3: pos-1}[d]
past.append(new_pos)
stack.append((pos, d))
stack.append((new_pos, -1))
k += 1
else: # d >= 4
k -= 1
if k == len(path):
return True
return False
发表于 2020-02-14 15:36:35
回复(0)
遍历matrix的每个元素，并对每个元素进行深搜，在每次深搜时用一个集合vis记录走过的路径：
class Solution: def hasPath(self, matrix, m, n, path): if m == 0&nbs***bsp;n == 0: return False def dfs(i, j, level): if level >= len(path) - 1: return True r = False for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: if 0 <= x < m and 0 <= y < n and (x, y) not in vis and matrix[x*n+y] == path[level + 1]: vis.add((x, y)) r = r&nbs***bsp;dfs(x, y, level + 1) return r res = False for i in range(m): for j in range(n): if matrix[i*n+j] == path[0]: vis = set([(i, j)]) res = res&nbs***bsp;dfs(i, j, 0) return res
发表于 2020-02-14 15:10:48
回复(0)
# -*- coding:utf-8 -*- # 解体思路：回溯法+深度优先搜素，结束条件：矩阵中找到一条路径与path匹配（长度相等且每个字符相等） # 判断当前字符是否计入路径的条件：1.坐标不越界 2.字符与path预期相等 3.该字符没有被访问过 class Solution: def hasPath(self, matrix, rows, cols, path): # write code here if not matrix&nbs***bsp;rows < 1&nbs***bsp;cols < 1&nbs***bsp;not path: return False index = 0 visited = [[False for j in range(0, cols)] for i in range(0, rows)] def hasPathCore(matrix, row, col, index, path): flag = False if 0 <= row < rows and 0 <= col < cols and matrix[row * cols + col] == path[index] and not visited[row][col]: if index + 1 == len(path): return True index += 1 visited[row][col] = True flag = hasPathCore(matrix, row + 1, col, index, path) \ &nbs***bsp;hasPathCore(matrix, row, col + 1, index, path) \ &nbs***bsp;hasPathCore(matrix, row - 1, col, index, path) \ &nbs***bsp;hasPathCore(matrix, row, col - 1, index, path) if not flag: index -= 1 visited[row][col] = False return flag for i in range(0, rows): for j in range(0, cols): if hasPathCore(matrix, i, j, index, path): return True return False
发表于 2020-01-21 18:40:04
回复(0)
# -*- coding:utf-8 -*- class Solution: def hasPath(self, matrix, rows, cols, path): # write code here # 回溯算法 # 在循环中查找每次的字符串首字母 # 给定的数组是一行的，rows，cols告诉一共包含几行几列的数据 # 可能有多个False，只要有一个True，就算成功 # 找到第一个点后开始嵌套 for i in range(rows): for j in range(cols): judge=[True]*len(matrix) if self.ispath(matrix,rows,cols,i,j,path,judge): return True return False def ispath(self,matrix,rows,cols,i,j,path,judge): #判断i，j点开始的路径是否是path if path=='': #先确认path已经空了 return True if i>=rows&nbs***bsp;j>=cols&nbs***bsp;i<0&nbs***bsp;j<0: #再确认i，j没有超范围 return False if judge[i*cols+j]==False: #再确认是否碰到了标记false点 return False if matrix[i*cols+j]==path[0]: judge[i*cols+j]=False return ( self.ispath(matrix,rows,cols,i-1,j,path[1:],judge)&nbs***bsp; self.ispath(matrix,rows,cols,i+1,j,path[1:],judge)&nbs***bsp; self.ispath(matrix,rows,cols,i,j-1,path[1:],judge)&nbs***bsp; self.ispath(matrix,rows,cols,i,j+1,path[1:],judge) ) #上下左右 else: return False
发表于 2019-12-05 15:11:18
回复(0)
从矩阵中的值为路径的第一个字母开始进行dfs
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
#构造矩阵
m=[]
c=0
for i in range(rows):
l=[]
for j in range(cols):
l.append(matrix[c])
c+=1
m.append(l)
d=[[1,0],[-1,0],[0,1],[0,-1]]
#定义dfs函数
def dfs(x,y,path):
if not path:
return True
for dx,dy in d:
if 0<=x+dx<rows and 0<=y+dy<cols and (x+dx,y+dy) not in visited and m[x+dx][y+dy]==path[0]:
visited.add((x+dx,y+dy))
if dfs(x+dx,y+dy,path[1:]):
return True
visited.remove((x+dx,y+dy))
#已经走过的路记录下来
visited=set()
for i in range(rows):
for j in range(cols):
#以第一个字母为起点
if m[i][j]==path[0]:
visited.add((i,j))
if dfs(i,j,path[1:]):
return True
visited.remove((i,j))
编辑于 2019-11-23 00:01:25
回复(0)
class Solution: def hasPath(self, matrix, rows, cols, path): if not path: return True self.rows, self.cols = rows, cols for j in range(cols): for i in range(rows): if matrix[i*cols+j] == path[0] and self.hasPathAux(matrix, [(i,j)], path[1:]): return True return False def hasPathAux(self, matrix, mark, path): (i,j) = mark[-1] return not path or (i - 1 >= 0) and ((i-1,j) not in mark) and (matrix[(i-1)*self.cols+j] == path[0]) and self.hasPathAux(matrix, mark+[(i-1,j)], path[1:]) or (i + 1 < self.rows) and ((i+1,j) not in mark) and (matrix[(i+1)*self.cols+j] == path[0]) and self.hasPathAux(matrix, mark+[(i+1,j)], path[1:]) or (j - 1 >= 0) and ((i,j-1) not in mark) and (matrix[i*self.cols+(j-1)] == path[0]) and self.hasPathAux(matrix, mark+[(i,j-1)], path[1:]) or (j + 1 < self.cols) and ((i,j+1) not in mark) and (matrix[i*self.cols+(j+1)] == path[0]) and self.hasPathAux(matrix, mark+[(i,j+1)], path[1:])
编辑于 2019-10-19 14:48:17
回复(0)
class Solution: def hasPath(self, matrix, rows, cols, path): self.is_visited = [[0 for i in range(cols)] for i in range(rows)] self.matrix = matrix self.rows = rows self.cols = cols self.length = len(path) for i in range(rows): for j in range(cols): if self.hasPathCore(i, j, path, 0): return True return False def hasPathCore(self, row, col, path, str_ind): if str_ind >= self.length: return True if self.judge_val(row, col) and path[str_ind] == self.matrix[row][col]: self.is_visited[row][col] = 1 if self.hasPathCore(row + 1, col, path, str_ind + 1) or self.hasPathCore(row - 1, col, path, str_ind + 1) or self.hasPathCore( row, col + 1, path, str_ind + 1) or self.hasPathCore(row, col - 1, path, str_ind + 1): return True else: self.is_visited[row][col] = 0 return False def judge_val(self, row, col): if 0 <= row < self.rows and 0 <= col < self.cols and not self.is_visited[row][col]: return True else: return False
求问这个写法哪里错了呀，本地可以正常运行，提示的错误用例答案也是对的，但是他这确报错。
不通过
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为0.00%
用例:
"ABCESFCSADEE",3,4,"ABCCED"
对应输出应该为:
true
你的输出为:
string index out of range
答案错误:您提交的程序没有通过所有的测试用例
case通过率为0.00%
用例:
"ABCESFCSADEE",3,4,"ABCCED"
对应输出应该为:
true
你的输出为:
string index out of range
发表于 2019-08-26 00:14:20
回复(0)
# -*- coding:utf-8 -*- class Solution: def hasPathCore(self, matrix, rows, cols, row, col, path, path_index, visited): if len(path) == path_index: return True if row >= 0 and row < rows and col >= 0 and col < cols and matrix[row * cols + col] == path[path_index] and not visited[row * cols + col]: visited[row * cols + col] = True if self.hasPathCore(matrix, rows, cols, row, col - 1, path, path_index + 1, visited) or self.hasPathCore(matrix, rows, cols, row - 1, col, path, path_index + 1, visited) or self.hasPathCore(matrix, rows, cols, row, col + 1, path, path_index + 1, visited) or self.hasPathCore(matrix, rows, cols, row + 1, col, path, path_index + 1, visited): return True visited[row * cols + col] = False return False def hasPath(self, matrix, rows, cols, path): # write code here if matrix is None or rows < 1 or cols < 1 or path is None: return False for row in range(rows): for col in range(cols): visited = [False] * (rows * cols) if self.hasPathCore(matrix, rows, cols, row, col, path, 0, visited): print(True) return True print(False) return FalsePython简明代码
发表于 2019-08-18 16:58:58
回复(0)
# -*- coding:utf-8 -*- class Solution: def hasPath(self, matrix, rows, cols, path): # write code here #标志位初始化为False flag = [False]*len(matrix) for i in range(rows): for j in range(cols): if(self.judge(matrix,i,j,rows,cols,flag,path,0)): return True return False def judge(self,matrix,i,j,rows,cols,flag,path,k): #计算匹配的第一个元素转为一维数组的位置 index = i*cols+j if(k==len(path)-1): return True #递归终止条件 if(i<0 or i>=rows or j<0 or j>=cols or matrix[index]!=path[k] or flag[k]==True): return False #若k已经到达str末尾了，说明之前的都已经匹配成功了，直接返回true即可 if(k==len(path)-1): return True #已经走过此元素，将标志位设成true flag[index]=True #回溯，递归寻找，每次找到了就给k加一 if(self.judge(matrix,i-1,j,rows,cols,flag,path,k+1) or self.judge(matrix,i+1,j,rows,cols,flag,path,k+1) or self.judge(matrix,i,j-1,rows,cols,flag,path,k+1) or self.judge(matrix,i,j+1,rows,cols,flag,path,k+1) ): return True #走到这，说明这一条路不通，还原标志位返回上一个情况，再试其他的路径 flag[index]=False return False求问这个为什么不对~
发表于 2019-08-14 17:53:19
回复(0)
屁股都坐疼了，还好按自己想法写出来了（不用pycharm调试根本不知道哪里有问题）：
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.j = 0 self.ans = [] self.flag = [] def hasPath(self, matrix, rows, cols, path): def Path(row,col,matrix,rows,cols,path): if self.j == len(path): return if row<0 or row>rows-1 or col<0 or col>cols-1: return index = row*cols+col if matrix[index] == path[self.j] and self.flag[index]==0: self.flag[index] = 1 self.ans.append(index) self.j += 1 if self.j == len(path): return Path(row,col+1,matrix,rows,cols,path) Path(row,col-1,matrix,rows,cols,path) Path(row+1,col,matrix,rows,cols,path) Path(row-1,col,matrix,rows,cols,path) if self.j == len(path): return self.j -= 1 self.ans.pop() self.flag[index] = 0 self.flag = [0] * len(matrix) for i,x in enumerate(matrix): if x == path[0]: row = i//cols col = i%cols Path(row,col,matrix,rows,cols,path) if len(self.ans) == len(path): return True return False
发表于 2019-08-09 22:13:50
回复(0)
class Solution:
def hasPath(self, matrix, rows, cols, path):
if not matrix:#没有返回False
return False
if not path:
return True#没有path返回True
x = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]#矩阵是一行，生成一个cols行rows列的矩阵
#matrix=[1,2,3,4,5,6,7,6,5] x=[[1, 2, 3], [4, 5, 6], [7, 6, 5]]
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] = ''
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]#在上述上下左右遍历后该点已经访问过
return False#之前情况都不满足，返回False
else:
return False
对一个牛油思路的解释
编辑于 2019-10-06 20:56:05
回复(0)
# -*- coding:utf-8 -*- class Solution: def hasPath(self, matrix, rows, cols, path): # write code here self.flags = [0 for _ in range(len(matrix))] self.matrix, self.rows, self.cols, self.path = matrix, rows, cols, path for i in range(rows): for j in range(cols): if self.search(i, j, 0): return True return False def search(self, i, j, k): index = self.cols * i + j if not 0 <= i < self.rows or not 0 <= j < self.cols or \ self.flags[index] or self.matrix[index] != self.path[k]: return False # 越界 or 已经走过 or 不是所需节点 if k == len(self.path) - 1: return True # 已经找完，不需要继续递归 self.flags[index] = 1 # 走过这个点，寻找下个点 if self.search(i+1, j, k+1) or self.search(i-1, j, k+1) or \ self.search(i, j+1, k+1) or self.search(i, j-1, k+1): return True # 四条路中有一条可以走通 self.flags[index] = 0 # 如果无法走通，要释放这个点，以防影响其他路线中走此点 return False
编辑于 2019-05-23 19:30:11
回复(0)
def hasPath(self, matrix, rows, cols, path):
if rows == 0 or cols == 0:
return False
matrix_mat = []
for i in range(rows):
temp = []
for j in range(cols):
temp.append(matrix[i*cols + j])
matrix_mat.append(temp)
for i in range(rows):
for j in range(cols):
if self.df***atrix_mat, i, j, path):
return True
return False
def dfs(self, matri***ath):
if len(path) == 0:
return True
if i < 0 or i >= len(matrix) or j < 0 or j >= len(matrix[0]) or path[0] != matrix[i][j]:
return False
# 如果以上不返还说明当前的matrix[i][j]等于path[0]
# 对上下左右进行搜索,令path=path[1:]
# 用一个temp保存当前值,将当前位置置为#,避免重复搜索
temp = matrix[i][j]
matrix[i][j] = "#"
if self.df***atrix, i+1, j, path[1:]):
return True
if self.df***atrix, i-1, j, path[1:]):
return True
if self.df***atrix, i, j+1, path[1:]):
return True
if self.df***atrix, i, j-1, path[1:]):
return True
# 用temp将当前位置重新置为原来的字母
matrix[i][j] = temp
return False
发表于 2019-05-18 11:19:59
回复(0)
问题信息
难度：
46条回答
1455收藏
109640浏览
通过挑战的用户
-
2023-03-07 09:36:39 -
2023-02-27 02:46:12
-
2022-09-13 21:57:01
-
2022-09-10 15:23:48 -
2022-09-08 12:00:40
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
分析：回溯算法 这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的 第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。 重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。 由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个 字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。 由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。 当矩阵中坐标为（row,col）的 格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符 如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。 一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置 class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { if(str==NULL||rows<=0||cols<=0) return false; bool *isOk=new bool[rows*cols](); for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) if(isHsaPath(matrix,rows,cols,str,isOk,i,j)) return true; } return false; } bool isHsaPath(char *matrix,int rows,int cols,char *str,bool *isOk,int curx,int cury) { if(*str=='\0') return true; if(cury==cols) { curx++; cury=0; } if(cury==-1) { curx--; cury=cols-1; } if(curx<0||curx>=rows) return false; if(isOk[curx*cols+cury]||*str!=matrix[curx*cols+cury]) return false; isOk[curx*cols+cury]=true; bool sign=isHsaPath(matrix,rows,cols,str+1,isOk,curx-1,cury) ||isHsaPath(matrix,rows,cols,str+1,isOk,curx+1,cury) ||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury-1) ||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury+1); isOk[curx*cols+cury]=false; return sign; } };