矩阵中的路径C++回溯算法

矩阵中的路径

http://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc

回溯算法的基本思想,先选中矩阵中任意一位置作为起点,与字符串首字母进行匹配,若匹配则选择当前位置前后左右四个邻居节点继续与字符串的下一字母进行匹配,以此类推,若不匹配则回溯到前一状态。如此反复,字符串匹配完毕为止。具体思路见代码注释。

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(str==nullptr || strlen(str)==0){
            return true;
        }
        if(rows<=0 || cols<=0){
            return false;
        }
        // 选择不同的起点
        for(int i=0; i<rows; ++i){
            for(int j=0; j<cols; ++j){
                if(hasPath(matrix, rows, cols, str, 0, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
    // 回溯核心
    // 这里rows/cols表示矩阵总的行列数(从1开始数),row/col表示当前回溯到的行列数(从0开始)
    // 故row的最大有效值为rows-1,col同。 
    // index表示当前比较的字符为str[index], 故index<=strlen(str)-1
    bool hasPath(char* matrix, int rows, int cols, char* str, 
                    int index, int row,  int col)
    {
        //边界条件
        if(strlen(str)==index){
            return true;
        }
        if(row>=rows || col>=cols || row<0 || col<0){
            return false;
        }

        // 如果矩阵中可以正确找到str[index]
        if(str[index]==matrix[row*cols+col]){
            // 记录当前矩阵元素
            int tmp = matrix[row*cols+col]; 
            // 将该元素设置为0, 表示已访问
            matrix[row*cols+col] = 0; 
            // 继续向下寻找,任一路径满足条件即可
            if ( hasPath(matrix, rows, cols, str, index+1, row, col+1) ||
                 hasPath(matrix, rows, cols, str, index+1, row, col-1) ||
                 hasPath(matrix, rows, cols, str, index+1, row+1, col) ||
                 hasPath(matrix, rows, cols, str, index+1, row-1, col) ){
                return true;
            }
            // 都不满足,复位之前的状态
            matrix[row*cols+col] = tmp;
        }
        return false;
    }


};
全部评论

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务