矩阵中的路径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-17 14:38
干个蛋,干不了一点!!!!我真服了,还没搞完,很急。&nbsp;今天ddl,活没干完直接通宵,刺激。食堂很好吃,感觉离职的时候会胖10斤。mt喜欢能直接干活的,没空指导我,很难受。每个人都是笑嘻嘻的,但是从他们聊天中都能感受到各种试探,我有点慌了大家真的nb,都能准时完成工作下班,我羡慕啊!!!!!每天好累,想离职了💔
牛客26106072...:能去字节实习说明你的能力挺被认可的,实习中的这种累更有利于个人职场成长,试着当熬夜打游戏一样熬一熬,实习的意义就是看自己的差距和适应能力,总比等到工作时各种不适应辞职要好得多吧?
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
07-01 23:23
郑州大学 Java
否极泰来来来来:牛客迟早有高三的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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