深度优先搜索(DFS)
从某个状态,不断转移状态直到无法转移,然后回退到前一步的状态,继续转移到其他状态,如此不断重复,直到找到最终解. ====> 递归函数
隐式的用到了栈(stack)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
#define MAXN 10000
int n,k;
int s[MAXN];
using namespace std;
bool dfs(int i,int sum){
if( i == n ) return sum == k;
if ( dfs(i+1 , sum) ) return true;
if ( dfs(i+1, sum + s[i] )) return true;
return false;
}
void input(){
cin >> n;
for(int i=0;i<n;i++) cin >> s[i];
cin >> k;
}
int main(){
input();
if (dfs(0,0)) cout << "YES";
else cout <<"NO";
return 0;
}
|
laking countiing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <iostream>
#include <cstdio>
#define MAXN 10000
using namespace std;
int N,M;
char field[MAXN][MAXN]={
{"W........WW."},
{".WWW.....WWW"},
{"....WW...WW."},
{".........WW."},
{".........W.."},
{"..W.......W."},
{".W.W.....WW."},
{"W.W.W.....W."},
{".W.W......W."},
{"..W.......W."}
};
void dfs(int x,int y){
field[x][y] = '.';
for(int dx=-1;dx<=1;dx++)
for(int dy=-1;dy<=1;dy++){
int nx=x+dx;
int ny=y+dy;
if( (0 <= nx && nx< N) && (0 <= ny && ny < M) && field[nx][ny]=='W') dfs(nx,ny);
}
return ;
}
void solve(){
int res = 0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++){
if(field[i][j] == 'W'){
dfs(i,j);
res++;
}
}
printf("%d\n",res);
}
void printLake(){
N=10;M=12;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++)
cout << field[i][j] ;
cout << endl;
}
}
int main(){
N=10;
M=12;
solve();
return 0;
}
|
宽度优先搜索(BFS)
总是优先搜索距离初始状态最近的状态,复杂度 = O(状态书 * 转移的方式)
显式利用队列(queue),搜索时首先将初始状态添加到队列里,此后从队列的最前端不断取出状态,吧从该状态可以转移到的状态中尚未访问过的部分加入队列,如此往返,直至队列被取空或是找到了问题的解
广度优先搜索思想
设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是：
- （1）从图中的某个顶点V出发，访问之；并将其访问标志置为已被访问，即visited[i]=1；
- （2）依次访问顶点V的各个未被访问过的邻接 点，将V的全部邻接点都访问到；
- （3）分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接 点”被访问，直到图中所有已被访问过的顶点的邻接点都被访问到。依此类推，直到图中所有顶点都被访问完为止 。
广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。
1
2
3
4
5
6
7
8
9
10
11
| W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
.........WW.
..W.......W.
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
|
1
2
3
4
5
6
7
8
9
10
11
| {W........WW.}
{.WWW.....WWW}
{....WW...WW.}
{.........WW.}
{.........W..}
{.........WW.}
{..W.......W.}
{.W.W.....WW.}
{W.W.W.....W.}
{.W.W......W.}
{..W.......W.}
|
2019蓝桥杯省赛–maze
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <bits/stdc++.h>
#include <string>
#include <queue>
using namespace std;
typedef pair<int ,int> State;
const int maxn = 1000;
const int row = 4;
const int col = 6;
char maze[row+1][col+1];
int visited[row+1][col+1];
string trace[row+1][col+1];
int X[] = {-1,0,1,0};
int Y[] = {0,1,0,-1};
string sarr[] = {"U","R","D","L"};
int x=1;
int y=1;
void bfs(){
queue<State> q;
q.push(State(x,y));
while( !q.empty() ){
State s = q.front();
q.pop();
if( x == row && y == col ) break;
for( int i = 0 ; i < 4; i++){
int nx = s.first + X[i];
int ny = s.second + Y[i];
if( nx >= 1 && nx <= row &&
ny >= 1 && ny <= col &&
maze[nx][ny] != '1'&&
visited[nx][ny] == 0 )
{
visited[nx][ny] = 1;
visited[nx][ny] = visited[s.first][s.second] +1;
trace[nx][ny] = trace[s.first][s.second] + sarr[i];
q.push(State(nx,ny));
}
}
}
cout <<"times:"<< visited[row][col] <<endl;
cout <<"order:"<< trace[row][col] <<endl;
}
int main(){
for(int i=1 ; i <= row ; i++)
for(int j= 1; j <= col ; j++)
visited[i][j] = 0;
visited[1][1] = 1;
for(int i=1 ; i <= row ; i++){
for(int j= 1; j <= col ; j++)
scanf("%c",&maze[i][j]);
getchar();
}
bfs();
return 0;
}
|
