c/c++语言开发共享牛客网中矩阵中的路径

牛客网的题目如下: 题目描述 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。 如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s …


牛客网的题目如下:

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

解决思想:

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

实现的代码

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) == '')         return false;      row = rows;     col = cols;     ma = matrix;     s = str;      vector < int >xs;      vector < int >ys;     int k;     int slen = strlen(str);     int *visits = new int[rows * cols];        for (int i = 0; i < rows; i++)         for (int j = 0; j < cols; j++) {         k = i * cols + j;         if (matrix[k] == str[0]) {             xs.push_back(i);             ys.push_back(j);         }         } int xlen = xs.size();     for (int i = 0; i < xlen; i++) {         memset(visits, 0, sizeof(int) * rows * cols);         visits[xs[i] * col + ys[i]] = 1;         if (bfs(visits, xs[i], ys[i], 0, slen))         return true;     }     return false;     }      bool bfs(int *visits, int startx, int starty, int curindex, int slen) {     static int dx[] = { 0, 1, 0, -1 };     static int dy[] = { -1, 0, 1, 0 };     queue < mypoint * >q;     mypoint *p0 = new mypoint(startx, starty, curindex);     q.push(p0);      while (!q.empty()) {         mypoint *p1 = q.front();         q.pop();         printf("x=%d y=%d index=%dn", p1->x, p1->y, p1->index);         if (p1->index == (slen - 1))         return true;          for (int i = 0; i < 4; i++) {         int xx = dx[i] + p1->x;         int yy = dy[i] + p1->y;         int kk = xx * col + yy;         if (visitislegal(xx, yy, visits)             && ma[kk] == s[p1->index + 1]) {             mypoint *p2 = new mypoint(xx, yy, p1->index + 1);             visits[kk] = 1;             q.push(p2);         }           }      }     return false;     }     bool visitislegal(int x, int y, int *visits) {      if (x < 0 || x >= row)         return false;      if (y < 0 || y >= col)         return false;      int k = x * col + y;     if (visits[k])         return false;      return true;     }   };  int main() {     char *matrix = "aaaaaaaaaaaa";     // char *str="aaaaaaaaaaaa";     char *str = "aaaaaaaaa";     int row = 3, col = 4;     solution s;     cout << "res = " << s.haspath(matrix, row, col, str) << endl;  } 

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/601240.html

(0)
上一篇 2021年5月9日
下一篇 2021年5月9日

精彩推荐