当前位置:网站首页>[depth first search] Ji suanke: a joke of replacement
[depth first search] Ji suanke: a joke of replacement
2022-07-06 18:46:00 【muse_ age】
The question :
Given a string , Find the separation scheme , Separate the string into non repeating numbers
Ideas :
Because the string length is less than 100, therefore n yes 2 digit .
You can separate them in groups , You can also work in groups of two
( It can be seen as walking through a one-dimensional maze , from S[0] Go to the S[n-1], One step at a time , Or take two steps .)
DFS(int index)// The subscript
prune :
(1) Feasibility pruning ( Transboundary ):if(index>=n)return;
(2) Repetitive pruning (vis Array ): If there have been numbers , There is no need to search
(3) Optimal pruning ( With global variables flag): If there is already a set of solutions , Then there is no need to search
To make a choice :
Mark the number
Digital join vector Array
DFS(index+1)// Take a step
Recall mark
vector.pop_back();
Mark the number
Digital join vector Array
DFS(index+2)// Take two steps
Recall mark
vector.pop_back();
#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool vis[100];
vector<int>num;
string s;
int n;
bool flag=false;
void dfs(int step){
if(flag){
return;
}
if(step>=s.size()){
for(int i=0;i<num.size();i++){
cout<<num[i]<<" ";
}
flag=true;
return;
}
if(!vis[s[step]-'0']){
vis[s[step]-'0']=true;
num.push_back(s[step]-'0');
dfs(step+1);
vis[s[step]-'0']=false;
num.pop_back();
}
if((s[step]-'0')!=0&&!vis[(s[step]-'0')*10+s[step+1]-'0'])
{
vis[(s[step]-'0')*10+s[step+1]-'0']=true;
num.push_back((s[step]-'0')*10+s[step+1]-'0');
dfs(step+2);
vis[(s[step]-'0')*10+s[step+1]-'0']=false;
num.push_back((s[step]-'0')*10+s[step+1]-'0');
}
}
int main(){
cin>>s;
dfs(0);
}
边栏推荐
- POJ 2208 已知边四面体六个长度,计算体积
- 解读云原生技术
- Method of accessing mobile phone storage location permission under non root condition
- Breadth first traversal of graph
- Alibaba cloud international ECS cannot log in to the pagoda panel console
- 巨杉数据库首批入选金融信创解决方案!
- First, look at K, an ugly number
- SQL injection Foundation
- Tree-LSTM的一些理解以及DGL代码实现
- ORACLE进阶(四)表连接讲解
猜你喜欢
openmv4 学习笔记1----一键下载、图像处理背景知识、LAB亮度-对比度
手写一个的在线聊天系统(原理篇1)
CSRF vulnerability analysis
From 2022 to 2024, the list of cifar azrieli global scholars was announced, and 18 young scholars joined 6 research projects
星诺奇科技IPO被终止:曾拟募资3.5亿元 年营收3.67亿
Introduction and case analysis of Prophet model
Easy to use PDF to SVG program
Coco2017 dataset usage (brief introduction)
被疫情占据的上半年,你还好么?| 2022年中总结
Hongke shares | plate by plate ar application in Beijing Winter Olympics
随机推荐
涂鸦智能在香港双重主板上市:市值112亿港元 年营收3亿美元
Jdbc driver, c3p0, druid and jdbctemplate dependent jar packages
Celery best practices
[Sun Yat sen University] information sharing of postgraduate entrance examination and re examination
Unity资源顺序加载的一个方法
Stm32+hc05 serial port Bluetooth design simple Bluetooth speaker
Atcoder a mountaineer
Nuc11 cheetah Canyon setting U disk startup
Maixll dock camera usage
From 2022 to 2024, the list of cifar azrieli global scholars was announced, and 18 young scholars joined 6 research projects
Automatic reservation of air tickets in C language
[sword finger offer] 60 Points of N dice
Shangsilicon Valley JUC high concurrency programming learning notes (3) multi thread lock
Excellent open source fonts for programmers
RedisSystemException:WRONGTYPE Operation against a key holding the wrong kind of value
STM32+MFRC522完成IC卡号读取、密码修改、数据读写
How are you in the first half of the year occupied by the epidemic| Mid 2022 summary
具体说明 Flume介绍、安装和配置
二叉搜索树
Some recruitment markets in Shanghai refuse to recruit patients with covid-19 positive