牛客网的题目如下:
题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径,
但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
解决思想:
- 首先找到访问的起点,就是目标字符串的第一个字符与矩阵中的该字符的所有位置找出来。
- 使用bfs,将起点位置,上下左右,都去访问,每访问矩阵中一个字符的时候,会判断该字符是否合法,合法性的判断标准为:
字符所在的位置,行x,列y,属于矩阵中,该字符没有已经被访问过, - 如果该字符和目标字符串的当前需要访问的字符相同,说明当前字符有可能是路径中的一员,需要保存当前访问的信息,并放入队列,当访问它的邻居的时候,
就可以把当前访问的下标,拿来使用, - 只要访问矩阵节点的保存的下标,与字符串的最后一个字符的下标相同,说明目前字符串中的字符完全访问完毕,路径就表示找到。
实现的代码
c/c++开发分享牛客网中矩阵中的路径实现的代码,只能满足牛客网的测试用例,当测试用例较全的时候,该代码无法通过,但可以用于学习下bfs,
#include<iostream> #include<queue> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; struct mypoint { int x; int y; int index; mypoint(int x1, int y1, int k):x(x1), y(y1), index(k) { }}; class solution { public: int row; int col; char *ma; char *s; bool haspath(char *matrix, int rows, int cols, char *str) { if ((*str) == '