矩阵中的路径

这个题目是《剑指Offer》的第十二题：

给定一个 m x n 的二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

如：

board:
["A","B","C","E"]
["S","F","C","S"]
["A","D","E","E"]

word: "ABCCED"

return: true

这种在二维数组中找路径的问题一般可以用深度优先搜索（DFS）算法来解决，这道题也不例外。以我目前的解题经验，这种题一般都是由内外两层函数构成。外层函数用来把二维数组中的每一个元素传入内层函数进行检查，如果检查成功则返回 true；内层函数就是用 DFS 的思想来递归调用自己，对传入元素的上下左右四个方向进行深度遍历，这个过程中需要用一个哈希表来避免重复遍历同一个元素，这个哈希表通常是一个和原二维数组一样大的 char 型的二维数组。在 C 语言中，char 就是小整数，如果我们只是用来存储 0 或 1 的值，那么用 char 类型就比用 int 类型的空间复杂度更好。

现在我们用上述模板来分析这道题。先看外层函数，外层函数部分各个题型大同小异，都是对原二维数组的每一个元素调用内层函数。我们假设外层函数名为 hasExist，内层函数名为 hasExistCheck，则解题框架就是：

bool hasExist(args list)
{
    for every elem in board {
        if hasExistCheck(elem) is true {
            return true
        }
    }
    return false
}

接着我们来看内层函数。我们现在要从上下左右四个方向对 elem 进行深度遍历，用的是递归思想。递归的函数总的来说分两步，一个是 base condition，也就是我们常说的递归退出条件。另一个则是递归调用自己。我们先来看内层函数的 base condition。什么时候退出递归呢？首先，我们这是匹配字符串，如果已经匹配完成了，那么就应该返回 true。如果 elem 的上下左右四个方向的坐标超出了原矩阵的范围，则返回 false。还有一个条件，那就是如果当前元素不等于当前要找的字符串元素或当前的元素已经被搜索过，返回 false。接着，我们考虑如何递归调用自己。目前我看到的有两种方法。一种方法是用“或” 操作符把四个方向的调用连接进来；另一种方法则是先定义一个坐标数组，如 char axis[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 然后在一个循环中调用自己。因为计算机中对于语句 A || B || C || D 的计算规则是依次计算表达式 A，B，C，D，如果发现有其中有一个为 true，则返回 true。所以两种方法从本质上来说，计算速度是相当的。我个人更喜欢用“或”表达式去写，简洁明了。

知道了这些之后，我们就可以把内层函数的框架写出来了：

bool hasExistCheck(args list)
{
    if match the end character {
        return true
    }
    if invalid coordinate {
        return false
    }
    if elem != current character || searched[elem] == true {
        return false
    }
    searched[elem] = true /* mark elem searched */
    bool res = hasExistCheck(x+1, y, word+1 ...) ||
        hasExistCheck(x-1, y, word+1 ...) ||
        hasExistCheck(x, y+1, word+1 ...) ||
        hasExistCheck(x, y-1, word+1 ...);
    if res == false {
        searched[elem] = false /* mark elem unsearched */
    }
    return res
}

值得说明的是，DFS 是用栈来进行搜索的，是一种图算法。它本质上是从一个节点出发，把该节点的所有邻居结点入栈，然后从栈顶开始判断是否是要找的元素，先判断是否搜索过，如果搜索过，我们把它出栈，继续判断下一个节点。如果它不是我们想要的节点，则我们把它标记为搜索过，把它出栈，再把它的所有邻居节点入栈……这样一直执行下去，直到找到我们想要的节点或栈为空结束。所以可以看出，DFS 本质上是一种回溯算法，当沿着一个方向找下去，如果没找到，它还得回到最初的位置，继续沿着另一个方向去寻找。而在我们这道题中，如果我们在一个方向寻找时，最初我们是不知道能不能寻找成功的。所以我们每找到一个满足要求的节点，我们就把这个节点标记为搜索过。但是如果最终我们在这个方向上寻找失败了，我们在回溯的过程中需要把之前标记“搜索过”的节点重新标记为“未搜索过”，以免影响其他方向搜索的结果，这一点是非常重要的。

知道了这些之后，我们就可以非常轻松地把代码写出来了，这里是我的提交记录。

以上。