DFS Introduction

Depth-first search is one of the most commonly used algorithms.

Posted by Dusign on 2019-10-25
Words 368 and Reading Time 1 Minutes
Viewed Times

DFS 是搜索的手段之一。它从某个状态开始,不断地转移状态直到无法转移,然后回退到前一步的状态,继续转移到其他状态,如此不断重复,直到找到最终的解为止。

Question

question

Analysis

从任意的 W 开始,不停地把临接的部分用 ‘ . ’ 代替。1次 DFS 后与初始的这个 W 连接的所有 W 就都被替换成了 ‘ . ’ ,因此直到图中不再存在 W 为止,总共进行 DFS 的次数就是答案了。8个方向共对应了8种状态转移,每个格子作为 DFS 的参数至多被调用一次,所以复杂度为 Ο(8 x N x M) = Ο(N x M)。

Solution

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
//
// dfs.cpp
// DFS
//
// Created by gang du on 2019/10/26.
// Copyright © 2019 dusign. All rights reserved.
//

#include <iostream>

using namespace std;

int N, M;
char field[100][101];

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 ++;
}
}
}
cout << res <<endl;
}

int main(){
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> field[i][j];
}
}
solve();
return 0;
}

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

...

00:00
00:00