1.DFS 和 BFS 基础

1.DFS

ans;

void  dfs(层数, 其他参数)
{
    if(出局判断)
    {
        更新答案;
        return;
    }

    (剪枝)

    for (枚举下一层可能的情况)
    {
        if (!vis[i])
        {
            vis[i] = true;
            dfs(层数+1, 其他参数);
            vis[i] = false;
        }    
    }
}

2.BFS

queue<int> q;

vis[1] = true;
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!vis[j])
        {
            vis[j] = true;
            q.push(j);
        }
    }
}

求解连通性问题

洛谷P8662

char mp[N][N];
int vis[N][N];
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int flag;
// dfs

void dfs(int x, int y)
{
    vis[x][y] = 1;
    if (mp[x][y + 1] == '#' && mp[x][y - 1] == '#' && mp[x - 1][y] == '#' && mp[x + 1][y] == '#')
        flag = 1;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + d[i][0], ny = y + d[i][1];
        if (vis[nx][ny] == 0 && mp[nx][ny] == '#')
            dfs(nx, ny);
    }
}

// bfs
void bfs(int x, int y)
{
    queue<PII> q;
    q.push({x, y});
    vis[x][y] = 1;
    while (q.size())
    {
        PII t = q.front();
        q.pop();
        int tx = t.first, ty = t.second;
        if (mp[tx][ty + 1] == '#' && mp[tx][ty - 1] == '#' && mp[tx + 1][ty] == '#' && mp[tx - 1][ty] == '#')
            flag = 1;
        for (int i = 0; i < 4; i++)
        {
            int nx = tx + d[i][0], ny = ty + d[i][1];
            if (vis[nx][ny] == 0 && mp[nx][ny] == '#')
            {
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> mp[i];
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (mp[i][j] == '#' && vis[i][j] == 0)
            {
                flag = 0;
                bfs(i, j); // dfs(i, j);
                if (flag == 0)
                    ans++;
            }
        }
    }
    cout << ans << endl;
}

八皇后

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

const int maxn = 1000;

int n, ans;
vector<int> s;
bool col[maxn], dg[maxn], udg[maxn]; // 列， 主对角线， 副对角线

void dfs(int u)
{
    if (u == n)
    {
        ans++;
        if (ans <= 3 && s.size() == n)
        {
            for (int i = 0; i < n; i++)		cout << s[i] << ' ';
            cout << endl;
        }
        return;
    }

    for (int i = 1; i <= n; i++)
        if (!col[i] && !dg[u + i - 1] && !udg[u - i + n]) // y=u,  x=i
        {
            s.push_back(i);
            col[i] = dg[u + i - 1] = udg[u - i + n] = true;
            dfs(u + 1);
            col[i] = dg[u + i - 1] = udg[u - i + n] = false;
            s.pop_back();
        }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    dfs(0);
    cout << ans;
}

2.剪枝

• 可行性剪枝：对当前状态进行检查，如果当前条件不合法就不再继续，直接返回

• 搜索顺序剪枝：搜索树有多个层次和分支，不同的搜索顺序会产生不同的搜索树形态，复杂度也相差很大

• 最优性剪枝：在最优化问题的搜索过程中，如果当前花费的代价已超过前面搜索到的最优解，那么本次搜索就没有继续进行下去的意义，直接退出

• 排除等效冗余：如果沿当前节点搜索它的不同分支，最后的结果是一样的，那么只搜索一个分支就够了

• 记忆化搜索：在递归的过程中，有许多分支被反复计算，会大大降低算法的执行效率。用记忆化搜索，将已经计算出来的结果保存起来，以后需要用到时直接取出结果，避免重复运算，从而提高了算法的效率。记忆化搜索主要应用于动态规划