牛客网中矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径,
但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

解决思想:

  • 首先找到访问的起点,就是目标字符串的第一个字符与矩阵中的该字符的所有位置找出来。
  • 使用bfs,将起点位置,上下左右,都去访问,每访问矩阵中一个字符的时候,会判断该字符是否合法,合法性的判断标准为:
    字符所在的位置,行x,列y,属于矩阵中,该字符没有已经被访问过,
  • 如果该字符和目标字符串的当前需要访问的字符相同,说明当前字符有可能是路径中的一员,需要保存当前访问的信息,并放入队列,当访问它的邻居的时候,
    就可以把当前访问的下标,拿来使用,
  • 只要访问矩阵节点的保存的下标,与字符串的最后一个字符的下标相同,说明目前字符串中的字符完全访问完毕,路径就表示找到。

实现的代码

本文实现的代码,只能满足牛客网的测试用例,当测试用例较全的时候,该代码无法通过,但可以用于学习下bfs,

include<iostream>#include<queue>#include<cstring>#include<cstdlib>#include<cstdio>usingnamespacestd;struct MyPoint {   intx;   inty;   intindex;     MyPoint(intx1,inty1,intk):x(x1), y(y1), index(k) {}};class Solution {  public:   introw;   intcol;   char*ma;   char*s;    bool hasPath(char *matrix, int rows, int cols, char *str) {   if((*str) =='\0')        returnfalse;    row = rows;    col = cols;    ma = matrix;    s = str;   vector<int>xs;     vector<int>ys;   intk;   intsLen =strlen(str);   int*visits =newint[rows * cols];   for(inti = 0; i < rows; i++)        for(intj = 0; j < cols; j++) {        k = i * cols + j;        if(matrix[k] == str[0]) {            xs.push_back(i);            ys.push_back(j);        }        }intxLen = xs.size();   for(inti = 0; i < xLen; i++) {        memset(visits, 0,sizeof(int) * rows * cols);        visits[xs_* col + ys_] = 1;        if(bfs(visits, xs_, ys_, 0, sLen))        returntrue;    }   returnfalse;    }    bool bfs(int *visits, int startX, int startY, int curIndex, int sLen) {   staticintdx[] = { 0, 1, 0, -1 };   staticintdy[] = { -1, 0, 1, 0 };   queue< MyPoint * >q;    MyPoint *p0 =newMyPoint(startX, startY, curIndex);    q.push(p0);   while(!q.empty()) {        MyPoint *p1 = q.front();        q.pop();        printf("x=%d y=%d index=%d\n", p1->x, p1->y, p1->index);        if(p1->index == (sLen - 1))        returntrue;        for(inti = 0; i < 4; i++) {        intxx = dx_+ p1->x;        intyy = dy_+ p1->y;        intkk = xx * col + yy;        if(visitIsLegal(xx, yy, visits)            && ma[kk] == s[p1->index + 1]) {            MyPoint *p2 =newMyPoint(xx, yy, p1->index + 1);            visits[kk] = 1;            q.push(p2);        }        }    }   returnfalse;    }    bool visitIsLegal(int x, int y, int *visits) {   if(x < 0 || x >= row)        returnfalse;   if(y < 0 || y >= col)        returnfalse;   intk = x * col + y;   if(visits[k])        returnfalse;   returntrue;    }};int main(){   char*matrix ="AAAAAAAAAAAA";   // char *str="AAAAAAAAAAAA";   char*str ="AAAAAAAAA";   introw = 3, col = 4;    Solution s;   cout<<"res = "<< s.hasPath(matrix, row, col, str) <<endl;}______

评论

暂无评论