解题思路

1. 先写一个dfs函数：

• 当索引值超过边界，或当前的矩阵值与字符串相对应的符号不匹配，或者是当前元素已经被遍历过了，则返回False；
• 如果当前已经遍历完目标字符串了，则说明匹配上一条路径了。则直接返回True。
• 否则，给当前值赋值True，代表已经遍历过了。
• 如果这上下左右这四个方向至少有一个方向能找到路径，则返回True。
• 否则将该值的状态改为False，并将函数返回False。

2. 求路径的函数内：遍历矩阵的每一个元素，判断从某个元素开始是否有可行的路径。

代码

Python

class Solution:
    def dfs(self, matrix, n, m, i, j, word, k, flag):
        if i < 0 or i >= n or j < 0 or j >= m or (matrix[i][j] != word[k]) or flag[i][j]:
            return False

        if k == len(word) - 1:
            return True

        flag[i][j] = True
        if (self.dfs(matrix, n, m, i-1, j, word, k+1, flag)
            or self.dfs(matrix, n, m, i, j-1, word, k+1, flag)
            or self.dfs(matrix, n, m, i+1, j, word, k+1, flag)
            or self.dfs(matrix, n, m, i, j+1, word, k+1, flag)):
            return True

        flag[i][j] = False

        return False


    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        if len(matrix) == 0:
            return False

        n = len(matrix)
        m = len(matrix[0])

        flag = [[False for i in range(m)] for j in range(n)]

        for i in range(n):
            for j in range(m):
                if self.dfs(matrix, n, m, i, j, word, 0, flag):
                    return True

        return False

C++

#include <vector>
class Solution {
public:
    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])
        {
            return false;
        }

        if(k == (word.size() - 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) 
    {
        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;
    }
};