问搜索二维数组中的序列(每个条目仅访问一次)

EN

这是“编程面试的元素”(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中的条目，我知道如何使用递归解决问题。

但是，如果有一个额外的约束，即每个条目最多只能访问一次，我如何有效地解决这个问题呢？