回溯类问题框架
框架 回溯 问题
2023-09-14 09:15:27 时间
N叉树的前序遍历
void preorder(Node* node) {
cout << "value:" << node->val << endl;
for (Node* n : node->children) {
preorder(n);
}
return;
}
其实回溯,可不就是N叉树的前序遍历带上功能嘛。
回溯框架
vector<T> res;
void back_track(路径,选择列表){
if(满足结束条件){
res.push_back(路径);
}
for 选择 in 选择列表{
做选择
back_track(路径+1,选择列表);
撤销选择
}
}
示例
【C++】算法集锦(3):回溯,从入门到入土,七道试题精选、精讲、精练
4*4数独
#include<iostream>
#include<vector>
using namespace std;
bool check(vector<vector<int>>& vvec, int a, int b, int num) {
for (int i : vvec[a]) {
if (i == num) {
return false;
}
}
if (vvec[0][b] == num || vvec[1][b] == num || vvec[2][b] == num || vvec[3][b] == num) {
return false;
}
return true;
}
bool numbers_game(vector<vector<int>>& vvec, vector<int>& vec, int a, int b) {
if (b == 4) {
a++;
b = 0;
}
if (a == 4) {
cout << "OK" << endl;
return true;
}
for (int i : vec) {
if (check(vvec, a, b, i)) {
vvec[a][b] = i;
return numbers_game(vvec, vec, a, b+1);
}
vvec[a][b] = 0;
}
return false;
}
int main() {
vector<vector<int>> vvec = { {0,0,0,0},{0,0,0,0},{0,0,0,0} ,{0,0,0,0} };
vector<int> vec = { 1,2,3,4 };
cout << numbers_game(vvec, vec, 0, 0);
}
相关文章
- 第三百零六节,Django框架,models.py模块,数据库操作——创建表、数据类型、索引、admin后台,补充Django目录说明以及全局配置文件配置
- scrapy框架使用-crawlspider类,rule的使用,翻页功能,
- [ASP.NET Core 3框架揭秘] 依赖注入[2]:IoC模式
- Atitit 安全流程法 目录 1. 常见等安全措施方法2 1.1. 安全的语言 代码法,编译型 java2 1.2. 安全编码法2 1.3. 安全等框架类库 api2 1.4. 加密法2
- Atitit 知识点 文章 框架 结构 大纲 attilax 总结 艾提拉总结 技术掌握文档总结的 v5 s420.docx 1.1. Preface前言 序言1 2. 技术流程了解》》选型(标准
- 【项目实战】并发编程之Java集合框架中的一个线程安全的队列实现 ——BlockingQueue入门介绍
- Python Django框架学习06:Django 模型
- 【Android 插件化】“ 插桩式 “ 插件化框架 ( 获取插件入口 Activity 组件 | 加载插件 Resources 资源 )
- 【Android 插件化】“ 插桩式 “ 插件化框架 ( 注入上下文的使用 )
- Spring框架学习之第2节
- python3+selenium自动化测试框架详解