查看“︁10-搜索/01-深度优先搜索”︁的源代码


== 深度优先搜索（DFS） ==

DFS 从起点出发，沿着一条路径'''走到底'''，再回溯尝试其他路径。核心思想是'''递归'''。

=== 排列枚举 ===

输出 <math>1 \sim n</math> 的全排列：

<syntaxhighlight lang="cpp">
int n, a[15];
bool used[15];

void dfs(int step)
{
    if (step > n)
    {
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!used[i])
        {
            used[i] = true;
            a[step] = i;
            dfs(step + 1);
            used[i] = false; // 回溯
        }
}
</syntaxhighlight>

=== 组合枚举 ===

从 <math>n</math> 个中选 <math>m</math> 个：

<syntaxhighlight lang="cpp">
int n, m, a[15];

void dfs(int step, int start)
{
    if (step > m)
    {
        for (int i = 1; i <= m; i++)
            cout << a[i] << " ";
        cout << "\n";
        return;
    }
    for (int i = start; i <= n; i++)
    {
        a[step] = i;
        dfs(step + 1, i + 1);
    }
}
</syntaxhighlight>

=== 网格搜索 ===

<syntaxhighlight lang="cpp">
int n, m;
char g[105][105];
bool vis[105][105];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y)
{
    vis[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (vis[nx][ny] || g[nx][ny] == '#') continue;
        dfs(nx, ny);
    }
}
</syntaxhighlight>

[[Category:搜索]]
[[Category:三三文档]]