10-搜索/01-深度优先搜索

深度优先搜索（DFS）

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

排列枚举

输出 [math]\displaystyle{ 1 \sim n }[/math] 的全排列：

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; // 回溯
        }
}

组合枚举

从 [math]\displaystyle{ n }[/math] 个中选 [math]\displaystyle{ m }[/math] 个：

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);
    }
}

网格搜索

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);
    }
}