这是“编程面试的元素”(17.5)一书中的一个问题。问题是:
当A是一个矩阵,S是一个整数数组时,如果你能从A中的某一项开始,按S规定的顺序遍历A中的相邻项,我们就说S出现在A中。相邻项是顶部、底部、左侧和右侧的项。
例如,如果A=
[1 2 3
3 4 5
5 6 7]
S=1 3 4 6
则S在A中,因为A= 1,A1 = 3,A1 = 4,A2 =6
但如果S=1 2 3 4,则S不在A中。
如果可以多次访问A中的条目,我知道如何使用递归解决问题。
但是,如果有一个额外的约束,即每个条目最多只能访问一次,我如何有效地解决这个问题呢?
发布于 2019-06-12 03:06:44
如果访问被解释为“不按给定的顺序访问单元格”,也就是说,在算法过程中可以多次访问单元格,那么我能想到的最好的解决方案具有指数时间复杂度。
跟踪沿给定路径访问的单元格的要点:
from typing import Set, Tuple
def is_pattern_contained_in_grid(grid, S):
def traverse(x, y, s_idx, visited: Set[Tuple[int,int]]):
if (s_idx == len(S)):
return True
if ((x, y) in visited
or not( x >= 0 and y >= 0 and x < n and y < m)
or grid[x][y] != S[s_idx]):
return False
for adj_x, adj_y in ((x + 1, y),
(x - 1, y),
(x, y + 1),
(x, y - 1)):
if (traverse(adj_x, adj_y, s_idx + 1, visited.union({(x,y)}))):
return True
return False
if (not S):
return True
n = len(grid)
m = len(grid[0])
for i in range(n*m):
x = i % n
y = i // n
if (traverse(x, y, 0, set())):
return True
return False
# Some examples
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,7],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,5,6]))
https://stackoverflow.com/questions/39584214
复制相似问题