题解 | #矩阵中的路径#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool dfs(vector<vector<char>>& matrix, int n, int m, int i, int j, string word, int k, vector<vector<bool>>& flag){
        if (i<0||i>=n||j<0||j>=m||(matrix[i][j]!=word[k]||flag[i][j]==true)) {
            return false;
        }
        if (k==word.length()-1) {
            return true;
        }
        flag[i][j] = true;
        if(dfs(matrix, n, m, i-1, j, word, k+1, flag)||
        dfs(matrix, n, m, i+1, j, word, k+1, flag)||
         dfs(matrix, n, m, i, j-1, word, k+1, flag)||
          dfs(matrix, n, m, i, j+1, word, k+1, flag)){
            return true;
        }
        flag[i][j] = false;
        return false;        

    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if (matrix.size()==0) {
            return false;
        }
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector <bool>> flag(n, vector<bool>(m, false));
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if(dfs(matrix, n, m, i, j, word, 0, flag)){
                    return true;
                }
            }
        
        }
        return false;
    }
};

为了在n*m矩阵matrix中判断是否存在一条路径包括指定的字符串string word, 考虑使用递归的思想，即把问题分解为寻找下一个子字符串。具体而言，当判断当前节点为字符串中特定位置的字符时，则开始判断其上下左右的字符是否为字符串中的下一个字符，，依次递归。