当前位置:网站首页>DFS and BFS concepts and practices +acwing 842 arranged numbers (DFS) +acwing 844 Maze walking (BFS)
DFS and BFS concepts and practices +acwing 842 arranged numbers (DFS) +acwing 844 Maze walking (BFS)
2022-07-07 04:38:00 【_ Liu Xiaoyu】
DFS ( Deep search ), It is also said to be recursive
persistent : Keep searching to the end , Then go back to the next node
data structure : stack, Space :O(h) h: It's height
It does not have the shortest circuit property ( The idea is strange , Those with high space requirements )
Important concepts : to flash back , prune
BFS ( Wide search )
Calm and steady : Layer by layer search
data structure : queue, Space :O(2h) h: It's height
It has the shortest circuit property ( When the weight of each path is 1)
DFS Example explanation : Can be used to understand recursive Thought
acwing 842 Arrange numbers
Given an integer n, The digital 1∼n In a row , There will be many ways to arrange .
Now? , Please output all the arrangement methods in dictionary order .
Input format
All in one line , Contains an integer n.
Output format
Output all permutation schemes in dictionary order , One line for each scheme .
Data range
1≤n≤7
sample input :
3
sample output :
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
thought :
For the full permutation problem , You can draw the following search tree
The whole process of recursive function call
code:
// Backtracking is the stack callback automatically allocated in the system .
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N]; // Whether to traverse the points before saving == true It means that it has passed
void dfs(int u)
{
if(u == n)
{
// Explain that all positions are filled , From here 0 Start , stay main Function , Corresponding from 0 Start
for(int i=0; i<n; i++) cout << path[i] << ' ';
cout << endl;
return;
}
// Here is to determine which points can be selected
for(int i=1; i<=n; i++) // Here we need to find out which points have not been enumerated
{
if(!st[i])
{
path[u] = i;
st[i] = true;
dfs(u+ 1);
// Restore the scene
st[i] = false;
//path[u] = 0; // You can delete , Because the value here is overwritten
}
}
}
int main()
{
cin >> n;
dfs(0); // From 0 Start looking at
return 0;
}
Explain the above code flow :
BFS: Why can we find the shortest circuit
It is searched layer by layer , Only when the weights in the graph are the same , This search is the shortest way
DFS Generally, there is no commonly used framework , however BFS Wide search There are commonly used frameworks , So look down
Common solution steps :
- The initial state is put into the queue
- Put in while, Not empty
- stay while in Every time I get to the head of the team
- Expand Team head
- end
Pseudo code :
queue <- The initial state
while queue Not empty
{
t <- Team head
Expand t
}
Examples : acwing 844. Labyrinth
Given a n×m A two-dimensional array of integers , Used to represent a maze , The array contains only 0 or 1, among 0 Means the way to go ,1 Indicates an impassable wall .
first , There is a man in the upper left corner (1,1) It's about , It is known that the person can go up every time 、 Next 、 Left 、 Move a position in any right direction .
Excuse me, , The person moves from the upper left corner to the lower right corner (n,m) It's about , At least how many times you need to move .
Data assurance (1,1) Place and (n,m) The number at is 0, And there must be at least one path .
Input format
The first line contains two integers n and m.
Next n That's ok , Each row contains m It's an integer (0 or 1), Represents a complete two-dimensional array .
Output format
Output an integer , Represents the minimum number of moves from the upper left corner to the lower right corner .
Data range
1≤n,m≤100
sample input :
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
sample output :
8
Ideas :
- use g[][] Store maps , use d[][] Store starting point to n,m Distance of
- From the starting point, breadth first traverse the map
- When the map is traversed , The distance from the starting point to each point is calculated , Output d[n][m] that will do
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N]; // Store maps
int d[N][N]; // Storage distance
int n, m;
int bfs()
{
queue<PII> q;
q.push({
0, 0});
memset(d, -1, sizeof d);
d[0][0] = 0;
while(!q.empty())
{
PII start = q.front();
q.pop();
g[start.first][start.second] = 1; // I've been through
int dx[4] = {
-1, 0, 1, 0}, dy[4] = {
0, 1, 0 ,-1};
for(int i =0; i < 4; i++)
{
int x = start.first + dx[i], y = start.second + dy[i];
if(!g[x][y] && x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1) // It means you haven't walked , Description optional
{
g[x][y] = 1;
d[x][y] = d[start.first][start.second] + 1;
//cout << d[x][y] << endl;
q.push({
x, y});
}
}
}
// d The shortest distance of the path that can be walked has been saved in the array ( To {0,0})
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
memset(g, 1, sizeof g); // You can't go without initialization
for(int i = 0; i < n; i ++)
for(int j =0; j < m; j ++)
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
The following is the path code if you want to output
Ideas : Output backward from the last position
Method : use Pre[][] Save the location information of the previous point
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N]; // Store maps
int d[N][N]; // Storage distance
int n, m;
PII Pre[N][N]; // Save the points passed
int bfs()
{
queue<PII> q;
q.push({
0, 0});
memset(d, -1, sizeof d);
d[0][0] = 0;
while(!q.empty())
{
PII start = q.front();
q.pop();
g[start.first][start.second] = 1; // I've been through
int dx[4] = {
-1, 0, 1, 0}, dy[4] = {
0, 1, 0 ,-1};
for(int i =0; i < 4; i++)
{
int x = start.first + dx[i], y = start.second + dy[i];
if(!g[x][y] && x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1) // It means you haven't walked , Description optional
{
g[x][y] = 1;
Pre[x][y] = start;
d[x][y] = d[start.first][start.second] + 1;
//cout << d[x][y] << endl;
q.push({
x, y});
}
}
}
// The following is the output of the path from the end
int x = n - 1, y = m - 1;
while(x || y)
{
cout << x << ' ' << y << endl;
auto t = Pre[x][y];
x = t.first, y= t.second;
}
// d The shortest distance of the path that can be walked has been saved in the array ( To {0,0})
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
memset(g, 1, sizeof g); // You can't go without initialization
for(int i = 0; i < n; i ++)
for(int j =0; j < m; j ++)
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
The operation results are as follows :
边栏推荐
- Fiance donated 500million dollars to female PI, so that she didn't need to apply for projects, recruited 150 scientists, and did scientific research at ease!
- 用CPU方案打破内存墙?学PayPal堆傲腾扩容量,漏查欺诈交易量可降至1/30
- 视频融合云平台EasyCVR视频广场左侧栏列表样式优化
- Comment les tests de logiciels sont - ils effectués sur le site Web? Testez la stratégie!
- namespace基础介绍
- B站大佬用我的世界搞出卷积神经网络,LeCun转发!爆肝6个月,播放破百万
- Data security -- 12 -- Analysis of privacy protection
- Win11图片打不开怎么办?Win11无法打开图片的修复方法
- UltraEdit-32 warm prompt: right association, cancel bak file [easy to understand]
- The easycvr platform is connected to the RTMP protocol, and the interface call prompts how to solve the error of obtaining video recording?
猜你喜欢
[team learning] [34 issues] scratch (Level 2)
【自动化经验谈】自动化测试成长之路
[coded font series] opendyslexic font
NTU notes 6422quiz review (1-3 sections)
Win11远程桌面连接怎么打开?Win11远程桌面连接的五种方法
[OA] excel document generator: openpyxl module
Have you got the same "artifact" of cross architecture development praised by various industry leaders?
Ssm+jsp realizes the warehouse management system, and the interface is called an elegant interface
英特尔David Tuhy:英特尔傲腾技术成功的原因
EasyCVR视频广场点击播放时,主菜单高亮效果消失问题的修复
随机推荐
广告归因:买量如何做价值衡量?
【线段树实战】最近的请求次数 + 区域和检索 - 数组可修改+我的日程安排表Ⅰ/Ⅲ
程序员上班摸鱼,这么玩才高端!
图灵诞辰110周年,智能机器预言成真了吗?
sscanf,sscanf_ S and its related usage "suggested collection"
Station B boss used my world to create convolutional neural network, Lecun forwarding! Burst the liver for 6 months, playing more than one million
EasyCVR视频广场点击播放时,主菜单高亮效果消失问题的修复
Is there any way to bookmark the code in the visual studio project- Is there a way to bookmark code in a Visual Studio project?
Have you got the same "artifact" of cross architecture development praised by various industry leaders?
一图看懂!为什么学校教了你Coding但还是不会的原因...
架构实战训练营|课后作业|模块 6
组织实战攻防演练的5个阶段
機器人(自動化)課程的持續學習-2022-
Formation continue en robotique (automatisation) - 2022 -
jvm是什么?jvm调优有哪些目的?
UltraEdit-32 warm prompt: right association, cancel bak file [easy to understand]
Lessons and thoughts of the first SQL injection
论文上岸攻略 | 如何快速入门学术论文写作
微信能开小号了,拼多多“砍一刀”被判侵权,字节VR设备出货量全球第二,今日更多大新闻在此
Deeply cultivate the developer ecosystem, accelerate the innovation and development of AI industry, and Intel brings many partners together