题目描述（中等难度）

意思就是从某个字符出发，然后它可以向左向右向上向下移动，走过的路径构成一个字符串，判断是否能走出给定字符串的 word ，还有一个条件就是走过的字符不能够走第二次。

比如 SEE，从第二行最后一列的 S 出发，向下移动，再向左移动，就走出了 SEE。

ABCB，从第一行第一列的 A 出发，向右移动，再向右移动，到达 C 以后，不能向左移动回到 B ，并且也没有其他的路径走出 ABCB 所以返回 false。

解法一 DFS

我们可以把矩阵看做一个图，然后利用图的深度优先遍历 DFS 的思想就可以了。

我们需要做的就是，在深度优先遍历过程中，判断当前遍历元素是否对应 word 元素，如果不匹配就结束当前的遍历，返回上一次的元素，尝试其他路径。当然，和普通的 dfs 一样，我们需要一个 visited 数组标记元素是否访问过。

我们可以优化一下空间复杂度，我们之前是用了一个等大的二维数组来标记是否访问过。其实我们完全可以用之前的 board，我们把当前访问的元素置为 “$” ，也就是一个在 board 中不会出现的字符。然后当上下左右全部尝试完之后，我们再把当前元素还原就可以了。

在，看到另外一种标记和还原的方法。异或。

至于原理，因为 ASCII 码值的范围是 0 - 127，二进制的话就是 0000 0000 - 0111 1111，我们把它和 128 做异或，也就是和 1000 0000 。这样，如果想还原原来的数字只需要再异或 128 就可以了。

总

关键是对题目的理解，抽象到 DFS，题目就迎刃而解了。异或的应用很强。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^