• 题目难度：中等

  • 题目描述：
    请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
    例如:矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
  • 数据范围：0 ≤ n, m ≤ 20 , 1 ≤ len ≤ 25

  • 示例1:

    输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
    返回值：true

  • 思路：深度优先搜索

    提交结果：答案正确 运行时间：3ms 占用内存：448KB

    class Solution {
private:
  bool st[30][30];
  bool flag = false;
  int row, col;
  int strSize;
public:
  bool hasPath(vector<vector<char> >& matrix, string word) {
      row = matrix.size(), col = matrix[0].size();
      memset(st, false, sizeof st);
      strSize = word.size();

      for (int i = 0; i < row; ++i)
          for (int j = 0; j < col; ++j) 
              if (matrix[i][j] == word[0]) {
                  dfs(matrix, i, j, 0, word);
                  if (flag) return true;
              }
      return false;
  }

  void dfs(vector<vector<char> >& matrix, int x, int y, int cur, string word) {
      if (flag) return;
      if (x >= 0 && y >= 0 && x < row && y < col && !st[x][y] && matrix[x][y] == word[cur]) {
          if (cur == strSize - 1) {
              flag = true;
              return;
          }
          st[x][y] == true;
          dfs(matrix, x + 1, y, cur + 1, word);
          dfs(matrix, x, y + 1, cur + 1, word);
          dfs(matrix, x - 1, y, cur + 1, word);
          dfs(matrix, x, y - 1, cur + 1, word);
          st[x][y] == false;
       }
  }
}

    😘😘😘😘😘😘😘😘😘😘😘😘😘😘