algorithm - 在二维数组中搜索序列(每个条目只访问一次)

Question

这是《编程面试基础》(17.5)一书中的一道题。问题是:

当A是一个矩阵，S是一个整数数组时，如果你可以从A中的某个条目开始，并按照S规定的顺序遍历A中的相邻条目，我们就说S出现在A中。相邻的条目是top，bottom , 左边和右边的。

例如，如果A =

[1 2 3

3 4 5

5 6 7]

S = [1 3 4 6]

那么S在A中，因为A[0][0] = 1, A[1][0] = 3, A[1][1] = 4, A[2][1] = 6

但是如果 S = [1 2 3 4] 那么 S 不在 A 中。

如果可以多次访问 A 中的条目，我明白如何使用递归解决问题。

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

Answer 1

直截了当Depth First Search (DFS) 问题。

算法的概要如下:

1. 找到所有等于 S[0](序列中的第一个数字)的元素
2. 对于在步骤1中找到的所有未被访问的元素，做一个DFS，将节点标记为已访问。 只访问相邻节点当且仅当它没有被访问并且它是序列中的下一个数字

在第2步中每个节点最多访问一次。例如，一个棘手的情况是

S = [1,2,3,4]

A = [1,2,1]
    [2,3,2]
    [3,2,1]

这种情况没有答案，并且所有节点都被访问了一次:

// After first DFS starting at [0,0],  1 = visited, 0 = not visited
V = [1,1,0]
    [1,1,0]
    [1,0,0]
// After second DFS starting at [0,2], 1 = visited, 0 = not visited
V = [1,1,1]
    [1,1,1]
    [1,0,0]
// After third DFS starting at [2,2], 1 = visited, 0 = not visited
V = [1,1,1]
    [1,1,1]
    [1,1,1]
// Done, complexity = O(N*M) where the matrix is of size N X M

这是一个用 C++ 编写的示例代码:http://ideone.com/ganX9Z