矩阵中的路径

题目:设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵的任意一格开始,每一步可以在矩阵中向左右上下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bcfe”的路径,但矩阵中不包含“abfb”的路径,因为字符串的第一个字符b占据了矩阵的第一行第二个格子,路径不能再次进入这个格子

 回溯法,剑指offer代码:

       

   

从矩阵中第一行第一列的元素开始,直到遇到一个跟第一个字符一样的,然后再此点处往上下左右(只要在坐标盘内)走,只要有一个方向可以得到路径则返回true;否则依次回退,把标记过的点都撤销,再扫描下一个坐标点。直到某一次找到返回,或者没找到。

原文地址:https://www.cnblogs.com/libin123/p/12781492.html