面试题12：矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
知识点
递归，回溯法
Qiang的思路
这是一道非常棒的问题。在解题的过程中遇到了非常多的问题。
这道问题的解法还是相对容易一些的，对于一个矩阵，想寻找一个字符串在其中的路径，我们首先需要找到入口的位置。这个位置的寻找可以通过遍历矩阵，等于字符串的第一个元素的位置即为候选入口。
对于每一个候选入口需要对其进行检验，如果通过该入口可以找到一条路径，那么也就完成了寻找任务，如果每个候选入口都不满足路径，那么这个问题也就是无解的。
在入口的检验中，我们发现，因为找到了入口，我们就知道了寻找的起始点，那么便可以从该入口开始进行上下左右的依次探索寻找，同时，因为入口对应了字符串的第一个元素，所以该入口的位置不能被再次经过。这个时候我们就发现，需要定义一个标记矩阵来标识那些位置是经过的，不能被再次经过，所以在程序的开始需要对标记矩阵进行定义。
在探索的过程中，由于字符串的第一个元素已经找到位置，所以不用管第一个元素，从第二个元素开始继续探索即可，如果能找到合适的位置就继续进行探索，如果找不到就说明目前探索的路径是不对的，就可以结束当前路径的探索了。
接下来能够发现，在进行第三个元素的探索时实际上和第二个元素的探索一样。但是此时需要关注一下上下左右那些方面是被标记了的，被标记了的就不能再走了。OK，接下来就是一层一层的嵌套工程了，第四个，第五个……他们和之前的元素并无不同。
基于上述的简单思想，我们能够得到如下的解题代码。
import copy
# -*- coding:utf-8 -*-
class Solution:
def getResult(self, _flag, matrix, rows, cols, i, j, path):
flag=copy.deepcopy(_flag)
flag[i][j]=False
if path=='':
return True
if j>=1 and flag[i][j-1] and matrix[i*cols+j-1]==path[0]:
if self.getResult(flag, matrix, rows, cols, i, j-1, path[1:]):
return True
if j<=cols-2 and flag[i][j+1] and matrix[i*cols+j+1]==path[0]:
if self.getResult(flag, matrix, rows, cols, i, j+1, path[1:]):
return True
if i>=1 and flag[i-1][j] and matrix[(i-1)*cols+j]==path[0]:
if self.getResult(flag, matrix, rows, cols, i-1, j, path[1:]):
return True
if i<=rows-2 and flag[i+1][j] and matrix[(i+1)*cols+j]==path[0]:
if self.getResult(flag, matrix, rows, cols, i+1, j, path[1:]):
return True
return False
def hasPath(self, matrix, rows, cols, path):
# write code here
if path=='':
return True
flag=[[True for j in range(cols)] for i in range(rows)]
for i in range(rows):
for j in range(cols):
if matrix[i*cols+j]==path[0]:
if self.getResult(flag, matrix, rows, cols, i, j, path[1:]):
return True
return False
虽然思想非常简单，但是在编程的时候还是出现了非常多的问题，其中主要包括：
- 题目给的矩阵和字符串全部是字符串的形式给出，一开始不知道，走了很多的弯路。
- 对于Python在调用函数时传参为传引用的方式不是很熟，结果也浪费了很多的时间，后期可能对其写一篇文章。（在这段代码中，标记矩阵传递的只是引用，所以会被修改掉，影响最终结果。最后采用深拷贝的方式解决了这个问题）。
作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。
