剑指offer(C++)-JZ12:矩阵中的路径(算法-回溯)

简介: 剑指offer(C++)-JZ12:矩阵中的路径(算法-回溯)

题目描述:

请设计一个函数,用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如A矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

数据范围:0≤n,m≤20 ,1≤len≤25

示例:

输入:

[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"


返回值:

true

解题思路:

本题是回溯法的经典题目,也常用于解决迷宫问题。思路如下:


  1. 用flag记录当前点是否走过,结合矩阵数据和字符数据,运用dfs(深度优先遍历)进行路径探索。
  2. dfs中,若当前点出现下标越界、字符不匹配和已经走过的情况,则终止当前路;若字符匹配上了,则认为当前点满足要求,先暂时将flag设为true,并以该点为中心,继续向上下左右四个方向探索新的点位;若四个方向有路可走,则依次递进,直到有一条路径和字符串完全对应;若四个方向均无路,则回退一步,并将当前点的flag设为false。

总的来说,题目运用了回溯、深度优先遍历和递归的思想。

测试代码:

class Solution {
public:
    // 深度优先遍历
    bool dfs(vector<vector<char>>& matrix, int m, int n, int i, int j, string word, int k, vector<vector<bool>>& flag){
        // 下标越界、字符不匹配、已经遍历过,则false
        if(i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] != word[k] || flag[i][j])
            return false;
        // 刷新标识符
        flag[i][j]= true;
        // 字符串全部集齐,则true
        if(k == int(word.size() - 1))
            return true;
        // 上下左右四方向搜索,若有路通,则true    
        if(dfs(matrix, m, n, i - 1, j, word, k + 1, flag)
           || dfs(matrix, m, n, i + 1, j, word, k + 1, flag)
           || dfs(matrix, m, n, i, j - 1, word, k + 1, flag)
           || dfs(matrix, m, n, i, j +1 , word, k + 1, flag))
           return true;
        // 该点位无有效路径,倒退一步,此点未使用,所以重置flag
        flag[i][j] = false;
        return false;
    }
    // 是否有目标路径
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // 空数据判断
        int m = int(matrix.size());
        int n = int(matrix[0].size());
        if(m == 0 || n == 0)
            return false;
        // flag二维容器存放标识符,判断当前点是否走过
        vector<vector<bool>> flag(m,vector<bool>(n, false));
        // 遍历
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(dfs(matrix, m, n, i, j, word, 0, flag))
                    return true;
            }
        }
        return false;
    }
};


相关文章
|
3天前
|
算法 Java
算法系列之回溯算法
回溯算法(Backtracking Algorithm)是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,遇到正确解将其记录,直到找到了所有的解或者尝试了所有的可能为止。
23 4
算法系列之回溯算法
|
13天前
|
存储 监控 算法
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
37 15
|
13天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
41 12
|
4天前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
12 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
2月前
|
负载均衡 算法 安全
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
65 19
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
|
3月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
3月前
|
算法
|
3月前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
67 4