The so-called depth-first search is to use recursion and backtracking to consider “how to do the current step” every time, that is, what to do in the step step. After the current step is completed, recursion is used to consider the same step + 1 step what to do
For the basic model of dfs, just look at the template
(The picture is from “Aha! Algorithm”)
, of course, the application of depth-first search
1. Write out the full arrangement (one-dimensional) (can be seen as a one-dimensional maze)
1. Two-dimensional maze
Next, we briefly explain the basic issues that should be considered for these two types of topics:
1. Whether to count the number of steps
2. Do you want to compare the current coordinates with the target coordinates
3. Go in several directions (for the adjustment of the Next[][] array)
4. Do you want to take the repeated path (whether book[i][j]=0 after each dfs)
For each selection, it is an expansion. As for whether the expansion is successful, it depends on the judgment of the conditions.
So how to expand the pinch (realize the action of “walking”)
Then we have to define an array to achieve
int Next[4][2]={<!-- -->{0,1},{1,0},{0,-1},{-1,0}};</pre >
<p>Like the above code, it is to "walk" up, down, left, and right</p>
<pre>int Next[8][2]={<!-- -->{0,1},{1,1},{1,0},{0,-1},{1,-1 },{-1,-1},{-1,0},{-1,1}};
Like the above code is to go in 8 directions
In the process of walking, we should pay attention to whether we cross the boundary and whether we can continue walking
Pay attention to the details in the search, respectively define sx, sy, es, ey, tx, ty to record the corresponding amount
Not much to say, let’s study the topic directly
1. Rescue (two-dimensional maze)
2. Oil Deposits (two-dimensional maze class)
3.Prime Ring Problem (one-dimensional arrangement problem)
For this question, at the beginning, I didn’t notice that there may be more than one friend, and we should find the time from the angel to the friend who spent the shortest time with her, which is the correct answer. Therefore, the position of the angel is actually the starting point
#include<stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
int book[209][209];
char map[209][209];
int sx,sy,T;
int N,M;
int Next[4][2]={<!-- -->{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int t,int x,int y)
{
int tx,ty,k;
if(map[x][y]=='r')
{
if(t<T)
T=t;
return;
}
for(k=0;k<=3;k++)
{
tx=x + Next[k][0];
ty=y + Next[k][1];
if(tx<0||tx>N-1||ty<0||ty>M-1)
continue;
if(map[tx][ty]=='#'||book[tx][ty])
continue;
if(book[tx][ty]==0)
{
book[tx][ty]=1;
if(map[tx][ty]=='x')
dfs(t + 2,tx,ty);
else
dfs(t + 1,tx,ty);
book[tx][ty]=0;
}
}
}
int main()
{
int i,j;
while(scanf("%d%d", &N, &M)!=EOF)
{
memset(book,0,sizeof(book));
for(i=0;i<N;i ++ )
{
for(j=0;j<M;j++)
{
cin>>map[i][j];
if(map[i][j]=='a')
{
sx=i; sy=j;
}
}
}
T=999999;
book[sx][sy]=1;
dfs(0,sx,sy);
if(T!=999999)
printf("%d\\
",T);
else
printf("Poor ANGEL has to stay in the prison all his life.\\
");
}
return 0;
}
Then analyze the details of the code,
The initial input cannot be used scanf(“%c”, & amp;map[i][j])
This is because the newline character will also be entered, while using cin>>map[i][j] will not
When judging the restrictive conditions, it is to judge whether it has reached the end point, and compare the amount of time used, and record the least time. Because of the traversal of this question, it is not necessary to consider that the road that has already been walked, so book[i] [j] To restore after a dfs
At the same time, for the judgment of tx and ty, we must always remember that our character array starts recording from 0,
Then tx<0||tx>=N||ty<0||ty>=M is beyond the bounds
Ok, let’s look at the second question
Oil Deposits
For this question, the general search idea is similar,
However, there are differences in details from the above question.
For example, there may be more than one starting point for this question (that is, the dfs function is called multiple times in the main function)
The other is that the oil wells found after a search can no longer go (book[i][j] does not need to be restored)
The restriction in the dfs function is to encounter ‘*’
Oh, and can go 8 directions
Without further ado, let’s go to the code
#include<stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
int m,n,book[109][109];
char map[109][109];
int Next[8][2]={<!-- -->{0,1},{1,1},{1,0},{0,-1},{1,-1},{ -1,-1},{-1,0},{-1,1}};
int sum;
void dfs(int x,int y)
{
int tx,ty,i,j,k;
if(map[x][y]=='*')
return;
for(k=0;k<8;k++)
{
tx=x + Next[k][1];
ty=y + Next[k][0];
if(tx<0||tx>=m||ty<0||ty>=n||map[tx][ty]=='*'||book[tx][ty])
continue;
book[tx][ty]=1;
dfs(tx,ty);
\t\t
}
return;
}
int main()
{
int i,j;
while(scanf("%d%d", & amp;m, & amp;n)!=EOF & amp; & amp;m!=0)
{
memset(book,0,sizeof(book));
for(i=0;i<m;i ++ )
{
for(j=0;j<n;j++)
{
cin>>map[i][j];
//scanf("%c", & amp;map[i][j]); (wrong input method)
}
}
sum=0;
\t\t
for(i=0;i<m;i ++ )
{
for(j=0;j<n;j++)
{
if(map[i][j]=='@' & amp; & amp;book[i][j]==0)
{
book[i][j]=1;
dfs(i,j);
sum + + ;
}
}
}
printf("%d\\
",sum);
}
return 0;
}
Alright, let’s change the topic and play
Prime Ring Problem
For this question, due to the small amount of data and the sum of the numbers in two adjacent circles does not exceed 40, prime numbers can be screened out in advance.
The difference between the idea of this question and the above two questions is that the coordinates are not emphasized, but the number of steps.
The step here indicates the number of circles to stand in. Since the first circle is always 1, the step starts from 2. Note that we may be a little confused at the beginning, how to arrange the number of steps and the adjacent two The sum of the circles is a prime number, my suggestion here is,
For search problems, either the number of steps or the case in a two-dimensional path or both
Therefore, for this question, we only use the number of steps as a restriction, and for the arrangement of the prime number problem, we arrange to screen the number of steps in the process
For filtering, note that the last one is not only compared with the previous one, but also compared with 1
Ok, look at the code
#include<stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[45],book[30],n,num[30],T;
void clarify()
{
int i,j;
for(i=2;i<=40;i ++ )
{
for(j=2;j<i;j++)
{
if(i%j==0)
break;
}
if(j>=i)
a[i]=1;
}
return;
}
void dfs(int step)//step indicates which circle is currently standing
{
int i,j,k;
if(step==n + 1)
{
for(k=1;k<=n-1;k++)
printf("%d ",num[k]);
printf("%d\\
",num[n]);
return;
}
if(step<n)
for(i=2;i<=n;i ++ )
{
if(book[i]==0 & amp; & amp;a[i + num[step-1]]==1)
{
book[i]=1;
num[step]=i;
dfs(step + 1);
book[i]=0;
}
}
else
{
for(i=2;i<=n;i ++ )
{
if(book[i]==0 & amp; & amp;a[i + num[step-1]]==1 & amp; & amp;a[i + 1]==1)
{
book[i]=1;
num[step]=i;
dfs(step + 1);
book[i]=0;
}
}
}
return;
}
int main()
{
num[1]=1;
clarify();
while(scanf("%d", &n)!=EOF)
{
if(n)
T++;
printf("Case %d:\\
",T);
dfs(2);
printf("\\
");
}
return 0;
}
Search questions are broad and profound. If you want to really master them, you still need to do more questions and be more careful. Come on!