class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool dfs(vector<vector<char>> matrix, int i,int row, int col, string str) {
      //从矩阵的每一格子开始找,有点类似广度优先搜索，
    //矩阵可变大，变小,row,col代表当前格子大小
      //没有找到入口，返回false
      if(matrix[row][col]!=str[i]) return false;
      //如果找到，赋值为特殊字符*
        matrix[row][col]='*';
        i++;//表示当前正在匹配的字符
        //已经到了最后一个字符，已经匹配
        if(i==str.size()) return true;
        //此处为偏移量
        int dxy[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
        for(int j=0;j<4;j++)
        {
            row=row+dxy[j][0];//第一列是行的偏移量
            col=col+dxy[j][1];//第二列是列的偏移量
            //不能跑到原始矩阵的格子外面
            if(row>=0 && row< matrix.size() && col>=0 && col<matrix[0].size())
            {
                //找到第i个字符
                if(dfs(matrix, i,row, col, str))
                    return true;
            }
            //没有找到，或者超出边界，回溯到上一个位置
            row=row-dxy[j][0];
            col=col-dxy[j][1];
        }
        return false;
}
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // 参考tonyjxc
        int m = matrix.size();//行数
	    int n = matrix[0].size();//列数
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                //i,j代表回溯时矩阵的行列数
                if(dfs(matrix, 0,i, j, word))
                    return true;
            }
        }
	   return false;
    }
};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
 */
function hasPath( matrix , word ) {
    // write code here
    let rows = matrix.length;
    let cols = matrix[0].length;
    let flag = new Array((rows-1)*(cols-1)).fill(null);
    for(let i=0;i<rows;i++){
        for(let j=0;j<cols;j++){
            //循环遍历二维数组，找到七点啊等于word第一个元素的值，再递归判断四周是否有符合条件的第二个值
            if(judge(matrix,i,j,rows,cols,flag,word,0)){
                return true;
            }
        }
    }
    return false;
}
function judge(matrix,i,j,rows,cols,flag,word,k){
    //根据i和j计算匹配的第一个元素转为一维数组的未知
    let index=i*cols+j;
    //递归终止条件
    if(i<0||j<0||i>=rows||j>=cols||matrix[i][j]!=word[k]||flag[index]==true){
        return false;
    }
    //k的初始值为0，若k已经到达word末尾了，说明都已经匹配成功了，直接返回true
    if(k==word.length-1){
        return true
    }
    //要走的第一个位置为true，表示已经走过了
    flag[index]=true;
    //回溯，递归寻找 每次找到给k加1，找不到就还原
    if(judge(matrix,i-1,j,rows,cols,flag,word,k+1)||
       judge(matrix,i+1,j,rows,cols,flag,word,k+1)||
       judge(matrix,i,j-1,rows,cols,flag,word,k+1)||
       judge(matrix,i,j+1,rows,cols,flag,word,k+1)){
        return true
    }
    //走到这，说明这一条路不通，还原尝试其他路径
    flag[index]=false;
    return false;
}
module.exports = {
    hasPath : hasPath
};

class Solution:
    def hasPath(self , matrix , word ):
        # write code here
        if len(matrix)==0:
            return False
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.backtrack(matrix, word, 0, i, j) :
                    return True
    
    def backtrack(self,matrix, word, n, i, j):
        '''
        n表示当前对比的是word的第n个字符
        i,j表示当前的坐标
        '''
        if n==len(word):
            return True
        if i<0&nbs***bsp;i>=len(matrix)&nbs***bsp;j<0&nbs***bsp;j>=len(matrix[0])&nbs***bsp;matrix[i][j]!=word[n]:
            return False
        temp=matrix[i][j]
        matrix[i][j]='*'
        if self.backtrack(matrix,word,n+1,i+1,j)&nbs***bsp;self.backtrack(matrix,word,n+1,i-1,j)&nbs***bsp;self.backtrack(matrix,word,n+1,i,j+1)&nbs***bsp;self.backtrack(matrix,word,n+1,i,j-1):
            return True
        matrix[i][j]=temp
        return False
        
        

知识点：回溯 DFS
我为淑女月用Python：QwQ

class Solution:
    def dfs(self, matrix, word, i, j, pos):
        if i < 0 or i == len(matrix) or j < 0 or j == len(matrix[0]) or matrix[i][j] != word[pos]:
            return False
        if pos == len(word) - 1:
            return True
        tmp, matrix[i][j] = matrix[i][j], '.'
        ret = self.dfs(matrix, word, i, j - 1, pos + 1) or self.dfs(matrix, word, i, j + 1, pos + 1) \
              or self.dfs(matrix, word, i - 1, j, pos + 1) or self.dfs(matrix, word, i + 1, j, pos + 1)
        matrix[i][j] = tmp
        return ret

    def hasPath(self, matrix, word):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dfs(matrix, word, i, j, 0): # 如果以matrix[i][j]开头找到了一条路径！
                    return True
        return False

  /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for(int i=0; i < matrix.length ; i++){
            for(int j=0; j < matrix[i].length; j++){
               if( dfs(matrix, word, i , j , 0, visited)){
                   return true;
               }
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] matrix, String word, int i, int j,int k, boolean[][] visited){
        if(i <0 || j<0 || i >= matrix.length || j >= matrix[0].length || 
           visited[i][j] || k >= word.length() || matrix[i][j] != word.charAt(k)){
            return false;
        }
      
        if( k == word.length()-1){
            return true;
        }
        visited[i][j] = true;
        boolean res =  dfs(matrix , word , i + 1,j,k +1, visited) || 
              dfs(matrix , word , i -1 ,j, k+1, visited)||
             dfs(matrix , word , i ,j + 1, k+1, visited)||
             dfs(matrix , word , i ,j - 1, k+1, visited);
        
        visited[i][j] = false;
        return res;
    }

function hasPath( matrix ,  word ) {
    // write code here
    for(var i=0;i<matrix.length;i++){
      for(var j=0;j<matrix[0].length;j++){
          if(dfs(matrix,word,i,j,0)) return true;
      }
    }
    return false;
}

var dfs = function(matrix,word,i,j,k){
    if(i<0 || j<0 || i>=matrix.length||j>=matrix[0].length|| matrix[i][j]!=word[k]) return false;
    if(k==word.length-1) return true;
    var tmp = matrix[i][j];
    matrix[i][j] = '/';   //实际上每次回溯都会产生一个变量tmp，不会覆盖前面的值，变成'/'是为了不走重复路
    var res = dfs(matrix,word,i+1,j,k+1) || dfs(matrix,word,i-1,j,k+1)||
                dfs(matrix,word,i,j+1,k+1) || dfs(matrix,word,i,j-1,k+1);  
    matrix[i][j] = tmp;  //四周找不到的时候，将该值重置回原来的值
    return res;   //然后回溯上一个值，继续遍历它的四周，如果还是不符合，继续重置回溯的那个值
}
//参考CSDN大佬，原文链接：https://blog.csdn.net/my_z_1234/article/details/108056048

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def hasPath(self , matrix , word ):
        # write code here
        ##布尔矩阵
        visited=[[False for i in range(len(matrix[0]))]for j in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dfs(matrix,word,visited,i,j):
                    return True
        return False
       
    def dfs(self,matrix,word,visited,x,y):
        if not word:
            return True
        if not visited[x][y]:
            if matrix[x][y]==word[0]:
                if len(word)==1:
                    return True
                visited[x][y]=True
                ##down
                if x+1<len(matrix) and self.dfs(matrix,word[1:],visited,x+1,y):
                    return True
                ##up
                if x-1>=0 and self.dfs(matrix,word[1:],visited,x-1,y):
                    return True
                ##right
                if y+1<len(matrix[0]) and self.dfs(matrix,word[1:],visited,x,y+1):
                    return True
                ##left
                if y-1>=0 and self.dfs(matrix,word[1:],visited,x,y-1):
                    return True
                ##都不成立 返回上一节点 (x,y)位置变为没访问过的状态
                visited[x][y]=False
        return False

矩阵中的路径-DFS（利用递归特性实现DFS的回溯）

    public boolean hasPath (char[][] matrix, String word) {
        int rows = matrix.length;
        if (rows == 0) return false;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];//标识每个方格是否在路径里面，防止路径进入重复的方格里
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPath (matrix,i,j,visited,word,0)) return true;
            }
        }
        return false;
    }

    public boolean hasPath (char[][] matrix,int row,int col,boolean[][] visited,String word,int loc) {
        if (loc == word.length()) return true;
        int rows = matrix.length;
        int cols = matrix[0].length;
        if (row < 0 || row == rows || col < 0 || col == cols) return false;
        if (visited[row][col]) return false;
        if (matrix[row][col] == word.charAt(loc)){
            visited[row][col] = true;
            if (hasPath (matrix,row-1,col,visited,word,loc+1) || hasPath (matrix,row+1,col,visited,word,loc+1)
            || hasPath (matrix,row,col-1,visited,word,loc+1) || hasPath (matrix,row,col+1,visited,word,loc+1)){
                return true;
            }
            visited[row][col] = false;
        }
        return false;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] board, String word) {
        // write code here
              int  length1=board[0].length;//列数
      int  length2=board.length;//行数
        for(int i =0; i<length2;i++){
            for(int j=0;j<length1;j++){
                if(board[i][j]==word.charAt(0))
                 if(dfs(board,i,j,word,0))
                    return true;
                    
               
            }
        }
        return false;
    }


    public boolean dfs(char[][] board,int i, int j, String word, int u){
      int  length1=board[0].length;//列数
      int  length2=board.length;//行数
        //失败:先判断边界值
        if(i<0||i>=length2||j<0||j>=length1||board[i][j]!=word.charAt(u)){
            return false;
        }
        //成功:遍历到最后一个
        if(u==word.length()-1)
            return true;
        //覆盖原来防止重复
        char temp = board[i][j];
        board[i][j]= '#';
        //递归调用
        boolean res = dfs(board,i-1,j,word,u+1) || dfs(board,i+1,j,word,u+1) || dfs(board,i,j-1,word,u+1)
        || dfs(board,i,j+1,word,u+1) ;
        //递归结束
        board[i][j]= temp;
        return res;
        
    }
}

很经典的递归+回溯，注意用flag剪枝

class Solution {
private:
    // 先声明几个要用的变量，方便调用
    vector<vector<int> > visited;
    int flag = 0;
    int row, col;
    int str_size;
public:
    bool hasPath(vector<vector<char> >& matrix, string word) {
        row = matrix.size();
        col = matrix[0].size();
        str_size = word.size();
        visited = vector<vector<int> >(row, vector<int>(col, 0));
        for (int i = 0; i < matrix.size(); i++)
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == word[0]) {
                    // 第一个字母正确的时候，进入dfs
                    dfs(i, j, 0, word, matrix);
                    if (flag) {
                        return true;
                    }
                }
            }
        return false;
    }
    
    void dfs(int x, int y, int cur, string & word, vector<vector<char> > & matrix) {
        if (flag) return;
        if (x >= 0 && x < row && y >= 0 && y < col && visited[x][y] == 0 && matrix[x][y] == word[cur]) {
            if (cur == str_size - 1) {
                flag = 1;
                return;
            }
            visited[x][y] = 1;    
            dfs(x + 1, y, cur+1, word, matrix);
            dfs(x, y + 1, cur+1, word, matrix);
            dfs(x - 1, y, cur+1, word, matrix);
            dfs(x, y - 1, cur+1, word, matrix);
            visited[x][y] = 0;    // 回溯法
        }
    }
    
};

function hasPath( matrix ,  word ) {
    let m = matrix.length,n = matrix[0].length;
    function dfs(i,j,k=0){ // 第k个字符
        if(i<0 || i>=m || j<0 || j>=n||word[k]!==matrix[i][j] || matrix[i][j]===0) return false;
        if(k === word.length-1) return true;
        let temp = matrix[i][j];
        matrix[i][j] = 0;
        if(dfs(i,j+1,k+1) || dfs(i,j-1,k+1) || dfs(i-1,j,k+1) || dfs(i+1,j,k+1)){
            return true;
        } 
        matrix[i][j] = temp;
        return false;
    }
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(dfs(i,j,0)){
                return true;
            }
        }
    }
    return false;
}

import java.util.*;
public class Solution {
    char[][] matrix;
    String word;
    public boolean hasPath (char[][] matrix, String word) {
        // 使用递归完成回溯
        this.matrix = matrix;
        this.word = word;
        // 对每个节点dfs
        for(int row=0;row<matrix.length;row++){
            for(int col=0;col<matrix[0].length;col++){
                // 一旦找到则直接返回
                if(recur(row,col,0)==true){
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean recur(int row, int col, int len){
        // 以当前坐标为起点，向四个方向递归搜索
        
        // 如果当前递归target长度==word长度，返回true
        if(len==word.length())
            return true;
        // 如果越界，返回false
        if(row<0 || col<0 || row>=matrix.length || col>=matrix[0].length)
            return false;
        // 如果当前坐标值==特殊值，说明往回找到了用过的点，返回false
        if(matrix[row][col]=='_')
            return false;
        // 如果当前坐标值不等于下一个需要的值，返回false
        if(matrix[row][col]!=word.charAt(len))
            return false;
        // 暂存当前值，以特殊值标记当前节点为“用过”
        char temp = matrix[row][col];
        matrix[row][col] = '_';
        // 如果到这一步还没终止递归，说明截至到现在是一路匹配下来的，继续向四个方向递归, 暂存当前结果
        boolean result = recur(row+1,col,len+1) || recur(row,col+1,len+1) || recur(row-1,col,len+1) || recur(row,col-1,len+1);
        // 恢复当前值
        matrix[row][col] = temp;
        // 返回结果
        return result;
    }
}

class Solution
{
public:
    bool dfs(vector<vector<char>> &matrix, string word, int row, int col, int pos, vector<vector<bool>> &isVisited)
    {
        if (pos == word.size())
        {
            return true;
        }
        if (row < 0 || col < 0 || row == matrix.size() || col == matrix[0].size() || isVisited[row][col])
        {
            return false;
        }
        if (matrix[row][col] != word[pos])
        {
            return false;
        }

        isVisited[row][col] = true;
        bool ans = false;
        ans = ans || dfs(matrix, word, row - 1, col, pos + 1, isVisited);
        ans = ans || dfs(matrix, word, row + 1, col, pos + 1, isVisited);
        ans = ans || dfs(matrix, word, row, col - 1, pos + 1, isVisited);
        ans = ans || dfs(matrix, word, row, col + 1, pos + 1, isVisited);
        isVisited[row][col] = false;

        return ans;
    }

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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
*/
func hasPath( matrix [][]byte ,  word string ) bool {
    n,m:=len(matrix),len(matrix[0])
    vis:=make([][]bool,n)
    for i,_:=range vis{
        vis[i]=make([]bool,m)
    }
    dirs:=[][]int{[]int{0,1},[]int{1,0},[]int{0,-1},[]int{-1,0}}
    var ans bool
    var dfs func(int,int,string)
    dfs=func(i,j int,word string){
        if ans||vis[i][j]||matrix[i][j]!=word[0]{
            return
        }
        vis[i][j]=true
        word=word[1:]
        if len(word)==0{
            ans=true
            return
        }
        for _,dir:=range dirs{
            x,y:=i+dir[0],j+dir[1]
            if x>=0&&x<n&&y>=0&&y<m{
                dfs(x,y,word)
            }
        }
        vis[i][j]=false
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if matrix[i][j]==word[0]{
                dfs(i,j,word)
            }
        }
    }
    return ans
}