AcWing 23. 矩阵中的路径（C++）- dfs+有价值

我会带着你远行 2022-08-28 07:48 101阅读 0赞

题目链接：[https://www.acwing.com/problem/content/21/][https_www.acwing.com_problem_content_21]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution {
        
    public:
        bool hasPath(vector<vector<char>>& matrix, string &str) {
        
            
            for(int i=0;i<matrix.size();i++){
        
                for(int j=0;j<matrix[i].size();j++){
        
                    if(dfs(matrix,str,0,i,j)) return true;//第三个参数为每次执行的单词起点，然后依次枚举单词的每个字母
                }
            }
            
            return false;
        }
        
        bool dfs(vector<vector<char>>& matrix,string& str,int u,int x,int y){
        
            if(matrix[x][y]!=str[u]) return false;
            if(u==str.size()-1) return true;
            
            int dx[4]={
        -1,0,1,0},dy[4]={
        0,1,0,-1};//从时钟数字9开始顺时针旋转，x为横坐标，y为纵坐标
            char t=matrix[x][y];//将已使用过的字母改成一个特殊字母，以避免重复使用字符
            matrix[x][y]='*';
            
            for(int i=0;i<4;i++){
        
                int a=x+dx[i],b=y+dy[i];
                if(a>=0&&a<matrix.size()&&b>=0&&b<matrix[a].size()){
        
                    if(dfs(matrix,str,u+1,a,b)) return true;
                }
            }
            
            matrix[x][y]=t;//将使用过的字符还原
            return false;
        }
    };

[https_www.acwing.com_problem_content_21]: https://www.acwing.com/problem/content/21/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/903592cdccfb4c1d96eac95d58c7c178.png