本文共 5184 字，大约阅读时间需要 17 分钟。

深度优先搜索（DFS）应用实例

1. 迷宫问题

迷宫问题是一个经典的图遍历问题，通常使用深度优先搜索（DFS）来解决。DFS通过尽可能深入搜索一条路径，然后回溯，找到从起点到终点的路径。

实现代码

#include 
   
    #include 
    
     using namespace std;int n, m;string maze[110];bool vis[110][110];bool in(int x, int y) {    return (0 <= x && x < n && 0 <= y && y < m);}bool dfs(int x, int y) {    if (maze[x][y] == 'T') {        return true;    }    vis[x][y] = true;    for (int i = 0; i < 4; ++i) {        int tx = x + dir[i][0];        int ty = y + dir[i][1];        if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {            if (dfs(tx, ty)) {                return false;            }        }    }    vis[x][y] = false;    maze[x][y] = '.';    return false;}int main() {    cin >> n >> m;    for (int i = 0; i < n; ++i) {        cin >> maze[i];    }    int x, y;    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            if (maze[i][j] == 'S') {                x = i;                y = j;                break;            }        }        if (x != -1) {            break;        }    }    dfs(x, y);    return 0;}
    
   

解题思路

2. 象棋走马问题

在象棋中，马的走法具有跳跃特性，通常可以用DFS解决其路径问题。

实现代码

#include 
   
    using namespace std;char s[10][10];int dir[8][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};bool f = false;bool vis[10][10];int ans = 1000000;bool in(int x, int y) {    return (0 <= x && x < 10 && 0 <= y && y < 9);}void dfs(int x, int y, int step) {    vis[x][y] = true;    if (s[x][y] == 'T') {        f = true;        if (step < ans) {            ans = step;        }        return;    }    if (step >= 3) {        return;    }    for (int i = 0; i < 8; ++i) {        int tx = x + dir[i][0];        int ty = y + dir[i][1];        if (in(tx, ty) && s[tx][ty] != '#' && !vis[tx][ty]) {            dfs(tx, ty, step + 1);        }    }}int main() {    int x, y;    for (int i = 0; i < 10; ++i) {        for (int j = 0; j < 9; ++j) {            if (s[i][j] == 'S') {                x = i;                y = j;                break;            }        }        if (x != -1) {            break;        }    }    dfs(x, y, 0);    if (f) {        cout << "Yes " << ans << endl;    } else {        cout << "No" << endl;    }}
   

解题思路

3. 草地块问题

草地块问题可以通过DFS统计相连区域数量。

实现代码

#include 
   
    using namespace std;char mp[105][105];bool vis[105][105];int n, m;void dfs(int x, int y) {    if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '.') {        return;    }    vis[x][y] = true;    dfs(x - 1, y);    dfs(x + 1, y);    dfs(x, y - 1);    dfs(x, y + 1);}int main() {    cin >> n >> m;    int cnt = 0;    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            cin >> mp[i][j];        }    }    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            if (!vis[i][j] && mp[i][j] == '#') {                dfs(i, j);                cnt++;            }        }    }    cout << cnt << endl;}
   

解题思路

4. 树的子节点问题

树的子节点问题可以通过DFS计算每个节点的后代数量。

实现代码

#include 
   
    #include 
    
     using namespace std;vector
     
      
       > son;bool f[100005];int ans[100005];void dfs(int u) {    int ret = 1;    for (int i = 0; i < son[u].size(); ++i) {        ret += dfs(son[u][i]);    }    ans[u] = ret;    return ret;}int main() {    int n, x, y;    cin >> n;    son.resize(n + 1);    for (int i = 0; i < n - 1; ++i) {        cin >> x >> y;        son[x].push_back(y);        f[y] = true;    }    for (int i = 1; i <= n; ++i) {        if (!f[i]) {            int u = i;            break;        }    }    dfs(u);    for (int i = 1; i <= n; ++i) {        cout << ans[i] << endl;    }}
      
     
    
   

解题思路

5. 马可以走到哪里

马的走法问题可以通过DFS计算三步内可达的位置。

实现代码

#include 
   
    using namespace std;int n, m;char mp[105][105];bool vis[105][105];int a[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};void dfs(int x, int y, int step) {    if (x < 0 || x >= n || y < 0 || y >= m) {        return;    }    if (step > 3) {        return;    }    for (int i = 0; i < 8; ++i) {        int tx = x + a[i][0];        int ty = y + a[i][1];        if (tx < 0 || tx >= n || ty < 0 || ty >= m) {            continue;        }        if (step < 3 && mp[tx][ty] == 'B') {            dfs(tx, ty, step + 1);        }    }}int main() {    cin >> n >> m;    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            mp[i][j] = '.';        }    }    int x, y;    cin >> x >> y;    mp[x][y] = 'B';    dfs(x, y, 0);        // 输出可达的位置    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            if (vis[i][j]) {                cout << '#';            } else {                cout << '.';            }        }    }}
   

解题思路