力扣-剑指 Offer 12. 矩阵中的路径（C++）- 矩阵回溯

柔情只为你懂 2022-09-10 11:24 138阅读 0赞

题目链接：[https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/][https_leetcode-cn.com_problems_ju-zhen-zhong-de-lu-jing-lcof]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution {
        
    public: 
        bool exist(vector<vector<char>>& board, string word) {
        
            int row=board.size(),col=board[0].size();
            //思路：确定起点，确定完成之后，dfs每一步的方向
    
            for(int i=0;i<row;i++){
        //依次dfs遍历i,j是否为string word的起点
                for(int j=0;j<col;j++){
        
                    if(dfs(board,word,0,i,j)) return true;
                }
            }
    
            return false;
        }
    
        int dx[4]={
        -1,0,1,0},dy[4]={
        0,1,0,-1};//左上右下
    
        bool dfs(vector<vector<char>>& board,string& word,int u,int x,int y){
        //u表示当前搜索到第几个位置
            int row=board.size(),col=board[0].size();
    
            if(board[x][y]!=word[u]) return false;//当前点不是起点，直接返回
            if(u==word.size()-1) return true;//当前的节点是最后一个节点，即word为‘\0’，则返回
    
            char t=board[x][y];//保存当前位置是什么，用.代替表示用过
            board[x][y]='.';
    
            for(int i=0;i<4;i++){
        //遍历当前节点的四个方向
                int a=x+dx[i],b=y+dy[i];
    
                if(a<0||a>=row||b<0||b>=col||board[a][b]=='.') continue;
                if(dfs(board,word,u+1,a,b)) return true;//当前位置没有被用过，则dfs一下
            }
    
            board[x][y]=t;//恢复现场
    
            return false;
    
        }
    };

[https_leetcode-cn.com_problems_ju-zhen-zhong-de-lu-jing-lcof]: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/f348109853904a53b395c5233a762045.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/62b95c0890ec4b799aadb38af55e6abe.png