题解 | #矩阵中的路径#

和岛屿问题很像，递归加回溯。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
      if (matrix.empty()) {
        return false;
      }
      
      bool res = false;
      std::vector<std::vector<int>> visited(matrix.size(), std::vector<int>(matrix[0].size(), 0));
      
      for (int i = 0; i < matrix.size(); ++i) {
        for (int j = 0; j < matrix[0].size(); ++j) {
          if (matrix[i][j] == word[0]) {
            visited[i][j] = 1;
            res |= dfs(matrix, word, visited, i, j, 1);
            if (res) {
              return res;
            }
            visited[i][j] = 0;
          }
        }
      }
      
      return false;
    }
  private:
    bool dfs(const std::vector<std::vector<char>> &matrix, const std::string &word, std::vector<std::vector<int>> &visited, int i, int j, int idx) {
      if (idx == word.size()) {
        return true;
      }
      
      bool res = false;
      
      //  上下左右
      if (i > 0 && !visited[i - 1][j] && matrix[i - 1][j] == word[idx]) {
        visited[i - 1][j] = 1;
        res |= dfs(matrix, word, visited, i - 1, j, idx + 1);
        visited[i - 1][j] = 0;
      }
      
      if (i < matrix.size() - 1 && !visited[i + 1][j] && matrix[i + 1][j] == word[idx]) {
        visited[i + 1][j] = 1;
        res |= dfs(matrix, word, visited, i + 1, j, idx + 1);
        visited[i + 1][j] = 0;
      }
      
      if (j > 0 && !visited[i][j - 1] && matrix[i][j - 1] == word[idx]) {
        visited[i][j - 1] = 1;
        res |= dfs(matrix, word, visited, i, j - 1, idx + 1);
        visited[i][j - 1] = 0;
      }
      
      if (j < matrix[0].size() - 1 && !visited[i][j + 1] && matrix[i][j + 1] == word[idx]) {
        visited[i][j + 1] = 1;
        res |= dfs(matrix, word, visited, i, j + 1, idx + 1);
        visited[i][j + 1] = 0;
      }
      
      return res;
    }
};