C++回溯算法广度优先搜索举例分析

目录
  • 迷宫问题
  • N叉树的层序遍历
  • 腐烂的橘子
  • 单词接龙
  • 打开转盘锁

迷宫问题

假设有一个迷宫,里面有障碍物,迷宫用二维矩阵表示,标记为0的地方表示可以通过,标记为1的地方表示障碍物,不能通过。现在给一个迷宫出口,让你判断是否可以从入口进来之后,走出迷宫,每次可以向任意方向走。

代码实现:

namespace BFS {
	struct pair {
		int _x;
		int _y;

		pair(int x, int y)
			:_x(x)
			, _y(y)
		{}
	};

	bool mapBFS(vector<vector<int>> mat, int sx, int sy, int ex, int ey)
	{
		int row = mat.size();
		int col = mat[0].size();

		queue<pair> q;
		q.push(pair(sx, sy));
		vector<vector<int>> book(row, vector<int>(col, 0));
		book[sx][sy] = 1;

		int nextP[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

		while (!q.empty())
		{
			pair curPos = q.front();
			q.pop();
			if (curPos._x == ex && curPos._y == ey)
				return true;
			//一个点的所有可能延伸的点
			for (int i = 0; i < 4; i++)
			{
				int curX = curPos._x + nextP[i][0];
				int curY = curPos._y + nextP[i][1];

				if (curX < 0 || curX >= row || curY < 0 || curY >= col)
					continue;
				//没有走过且不是障碍物
				if (mat[curX][curY] == 0 && book[curX][curY] == 0)
				{
					book[curX][curY] = 1;
					//保存新的位置
					q.push(pair(curX, curY));
				}
			}
		}

		return false;
	}
}

int main()
{
	vector<vector<int>> mat{ {0, 0, 1, 0},
							 {1, 0, 0, 1},
							 {0, 0, 0, 0},
							 {1, 1, 0, 0} };
	int sx, sy, ex, ey;
	cin >> sx >> sy >> ex >> ey;
	cout << BFS::mapBFS(mat, sx, sy, ex, ey);

	return 0;
}

N叉树的层序遍历

问题描述:

给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。 树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。

代码实现:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if(!root)
            return result;
        queue<Node*> q;
        q.push(root);
        while(!q.empty())
        {
            //获取队列中的元素个数
            int sz = q.size();
            vector<int> rowV;
            while(sz--)
            {
                //保存当前元素在同一行
                Node* node = q.front();
                q.pop();
                rowV.push_back(node->val);
                //当前元素的孩子结点入队
                for(auto e : node->children)
                {
                    q.push(e);
                }
            }
            result.push_back(rowV);
        }

        return result;
    }
};

腐烂的橘子

问题描述:

在给定的网格中,每个单元格可以有以下三个值之一:

值 0 代表空单元格;

值 1 代表新鲜橘子;

值 2 代表腐烂的橘子。

每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。

本题可以先找到所有的腐烂橘子入队,用第一批带出新一批腐烂的橘子。 每一批橘子都会在一分钟之内腐烂,所以此题可以转化为求BFS执行的大循环的次数。这里的step的更新需要有一个标记,只有新的腐烂的橘子加入,step才++ 最后BFS执行完,说明所有可以被腐烂的都完成了,再去遍历grid,如果还有值为1的,说明没有办法全部腐烂,返回-1,如果没有,则返回step

代码实现:

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int step = 0;
        int row = grid.size();
        int col = grid[0].size();
        queue<pair<int, int>> q;
        //把所有腐烂的橘子入队
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 2)
                    q.push(make_pair(i, j));
            }
        }

        static int nextP[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0 ,1}};
        while(!q.empty()){
            int sz = q.size();
            bool flag = false;
            while(sz--){
                pair curPos = q.front();
                q.pop();
                for(int i = 0; i < 4; i++){
                    int curX = curPos.first + nextP[i][0];
                    int curY = curPos.second + nextP[i][1];
                    if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                        continue;
                    if(grid[curX][curY] == 1){
                        flag = true;
                        grid[curX][curY] = 2;
                        q.push(make_pair(curX, curY));
                    }
                }
            }
            if(flag)
                ++step;
        }

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 1)
                    return -1;
            }
        }

        return step;
    }
};

单词接龙

问题描述:

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列:

序列中第一个单词是 beginWord 。

序列中最后一个单词是 endWord 。

每次转换只能改变一个字母。

转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ,找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0。

示例 1:

输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

输出:5

解释:一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

1.通过BFS,首先用beginWord带出转换一个字符之后所有可能的结果

2.每一步都要把队列中上一步添加的所有单词转换一遍,最短的转换肯定在这些单词中,所有这些词的转换只能算一次转换,因为都是上一步转换出来的,这里对于每个单词的每个位置都可以用26个字母进行转换,所以一个单词一次转换的可能有:单词的长度*25

3.把转换成功的新词入队,进行下一步的转换

4.最后整个转换的长度就和BFS执行的次数相同

需要判断单词有没有被搜索过,是一个查询的过程,可以用哈希表

代码实现:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int step = 1;
        unordered_set<string> book;
        unordered_set<string> dict;
        book.insert(beginWord);
        for(string& ch : wordList)
            dict.insert(ch);
        queue<string> q;
        q.push(beginWord);

        while(!q.empty()){
            int size = q.size();
            while(size--){
                string curStr = q.front();
                q.pop();
                if(curStr == endWord)
                    return step;
                for(int i = 0; i < curStr.size(); i++){
                    string str1 = curStr;
                    for(char ch = 'a'; ch <= 'z'; ++ch){
                        str1[i] = ch;
                        //判断新的单词是否在词典中,且没被搜索过
                        if(dict.find(str1) != dict.end()
                        && book.find(str1) == book.end()){
                            q.push(str1);
                            book.insert(str1);
                        }
                    }
                }
            }
            ++step;
        }

        return 0;
    }
};

打开转盘锁

问题描述:

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0', ‘1', ‘2', ‘3', ‘4', ‘5', ‘6', ‘7', ‘8', ‘9' 。每个拨轮可以自由旋转:例如把 ‘9' 变为 ‘0',‘0' 变为 ‘9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000' ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。

深度优先不适合此题,递归深度太大,会导致栈溢出。

本题的密码为4位密码,每位密码可以通过拨动一次进行改变,注意这里的数的回环以及拨动的方向拨动方向:向前,向后。

回环:如果当前是9,0时,向前,向后拨动需要变成最小最大,而不是简单的自加自减。

0000一步旋转后的结果有:

0001 0009 0010 0090 0100 0900 1000 9000

代码实现:

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deaddict(deadends.begin(), deadends.end());
        //如果0000在死亡数字中,则永远也到不了
        if(deaddict.find("0000") != deaddict.end())
            return -1;
        queue<string> q;
        q.push("0000");
        //添加标记,已经搜索过的字符不再搜索
        unordered_set<string> book;
        book.insert("0000");
        int step = 0;
        while(!q.empty()){
            int size = q.size();
            while(size--){
                string curStr = q.front();
                q.pop();
                if(curStr == target)
                    return step;
                for(int i = 0; i < 4; i++){
                    string s1 = curStr;
                    string s2 = curStr;
                    //向前或向后旋转
                    s1[i] = s1[i] =='0' ? '9' : --s1[i];
                    s2[i] = s2[i] =='9' ? '0' : ++s2[i];
                    if(deaddict.find(s1) == deaddict.end()
                    && book.find(s1) == book.end()){
                        q.push(s1);
                        book.insert(s1);
                    }
                    if(deaddict.find(s2) == deaddict.end()
                    && book.find(s2) == book.end()){
                        q.push(s2);
                        book.insert(s2);
                    }
                }
            }
            ++step;
        }

        return -1;
    }
};

到此这篇关于C++回溯算法广度优先搜索举例分析的文章就介绍到这了,更多相关C++ 回溯算法 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • C++回溯法实例分析

    本文实例讲述了C++的回溯法,分享给大家供大家参考之用.具体方法分析如下: 一般来说,回溯法是一种枚举状态空间中所有可能状态的系统方法,它是一个一般性的算法框架. 解向量a=(a1, a2, ..., an),其中每个元素ai取自一个有限序列集Si,这样的解向量可以表示一个排列,其中ai是排列中的第i个元素,也可以表示子集S,其中ai为真当且仅当全集中的第i个元素在S中:甚至可以表示游戏的行动序列或者图中的路径. 在回溯法的每一步,我们从一个给定的部分解a={a1, a2, ..., ak}开始

  • c++回溯法解决1到9之间插入加减或空使运算结果为100

    目录 问题分析 代码展示 问题分析 这时我最近偶然看到的一道题目,发现实现起来还确实有些麻烦,所以把实现的过程记录下来. 这种要罗列出所有结果的问题,我一般是采用回溯法解决的,说的通俗一点就是暴力解法,去遍历所有的情况. 这个问题有一点比较难处理的地方就在于有这个"什么都不插入"这个选项,所以干脆单独拎出来解决.也就是先把1-9这9个数组相互组合,形成一个数组,比如: {1,2,3,4,5,6,7,8,9} {1,2,3,4,5,6,7,89} {1,2,3,4,5,6,78,9} {

  • C++回溯算法广度优先搜索举例分析

    目录 迷宫问题 N叉树的层序遍历 腐烂的橘子 单词接龙 打开转盘锁 迷宫问题 假设有一个迷宫,里面有障碍物,迷宫用二维矩阵表示,标记为0的地方表示可以通过,标记为1的地方表示障碍物,不能通过.现在给一个迷宫出口,让你判断是否可以从入口进来之后,走出迷宫,每次可以向任意方向走. 代码实现: namespace BFS { struct pair { int _x; int _y; pair(int x, int y) :_x(x) , _y(y) {} }; bool mapBFS(vector<

  • C++回溯算法深度优先搜索举例分析

    目录 扑克牌全排列 员工的重要性 图像渲染 被围绕的区域 岛屿数量 电话号码的字母组合 组合总数 活字印书 N皇后 扑克牌全排列 假如有编号为1~ 3的3张扑克牌和编号为1~3的3个盒子,现在需要将3张牌分别放到3个盒子中去,且每个盒子只能放一张牌,一共有多少种不同的放法. 解题思路:假定按照牌面值从小到大依次尝试,即将1号牌放入第一个盒子中.按此顺序继续向后走,放完第三个盒子时,手中的牌也已经用完,再继续往后则到了盒子的尽头.此时一种放法已经完成了,即这条路走到了尽头,需要折返,重新回到上一个

  • C语言全排列回溯算法介绍

    目录 前言 算法思想 完整代码 实验效果 总结 前言 本博文源于最近学习的递归算法,递归中遇到一个问题全排列的问题,我看见回溯特别神奇,特此记录一下.对比一下深度优先搜索与广度优先搜索,个人感觉这里的回溯像是一种递归树中的深度优先搜索的算法,他不断构造往下延伸的深度,使其达到完全编列 算法思想 比如3拿来举例,按照一般正常的话就是应该, 123 132 213 231 312 321 六种,先造出一个hashtable数组让其存储在各位是否使用,然后创建path的p数组将数字进行选填,递归树我花

  • C++实现广度优先搜索实例

    本文主要叙述了图的遍历算法中的广度优先搜索(Breadth-First-Search)算法,是非常经典的算法,可供C++程序员参考借鉴之用.具体如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次.注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历.图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search). 一.广度优先搜索(BFS)的

  • 浅谈Java实现回溯算法之八皇后问题

    目录 一.前言 二.浅谈递归 三.回溯算法 四.八皇后问题 五.八皇后变种 六.总结 一.前言 说起八皇后问题,它是一道回溯算法类的经典问题,也可能是我们大部分人在上数据结构或者算法课上遇到过的最难的一道题-- 二.浅谈递归 对于递归算法,我觉得掌握递归是入门数据结构与算法的关键,因为后面学习很多操作涉及到递归,例如链表的一些操作.树的遍历和一些操作.图的dfs.快排.归并排序等等. 递归的实质还是借助栈实现一些操作,利用递归能够完成的操作使用栈都能够完成,并且利用栈的话可以很好的控制停止,效率

  • 详解Go语言运用广度优先搜索走迷宫

    目录 一.理解广度优先算法 1.1.分析如何进行广度优先探索 1.2.我们来总结一下 1.3.代码分析 二.代码实现广度优先算法走迷宫 一.理解广度优先算法 我们要实现的是广度优先算法走迷宫 比如,我们有一个下面这样的迷宫 这个迷宫是6行5列 其中0代表可以走的路, 1代表一堵墙. 我们把墙标上言责, 就如右图所示. 其中(0,0)是起点, (6, 5)是终点. 我们要做的是, 从起点走到终点最近的路径. 这个例子是抛转隐喻, 介绍广度优先算法, 广度优先算法的应用很广泛, 所以, 先来看看规律

  • python回溯算法实现全排列小练习分享

    问题:输入列表L(不含重复元素),输出L的全排列. 如输入:L=[1,2,3] 则输出:[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 全排列问题,可以用回溯法解决,详细分析请参考东哥公众号:labuladong,看了之后醍醐灌顶. 先帖一个正确解法: ''' 回溯算法模板: from: labuladong公众号 result = [] def backtrack(选择列表,路径):     if 满足结束条

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • Java编程实现基于图的深度优先搜索和广度优先搜索完整代码

    为了解15puzzle问题,了解了一下深度优先搜索和广度优先搜索.先来讨论一下深度优先搜索(DFS),深度优先的目的就是优先搜索距离起始顶点最远的那些路径,而广度优先搜索则是先搜索距离起始顶点最近的那些路径.我想着深度优先搜索和回溯有什么区别呢?百度一下,说回溯是深搜的一种,区别在于回溯不保留搜索树.那么广度优先搜索(BFS)呢?它有哪些应用呢?答:最短路径,分酒问题,八数码问题等.言归正传,这里笔者用java简单实现了一下广搜和深搜.其中深搜是用图+栈实现的,广搜使用图+队列实现的,代码如下:

  • python广度优先搜索得到两点间最短路径

    前言 之前一直写不出来,这周周日花了一下午终于弄懂了, 顺便放博客里,方便以后忘记了再看看. 要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径. 广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数 思路 广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索: 比如下图: 从0结点开始搜索的话,一开始是0.将0加入队列中: 然后

随机推荐