1. DFS 和 BFS 基础
DFS
ans;void dfs(层数, 其他参数)
{if(出局判断){更新答案;return;}(剪枝)for (枚举下一层可能的情况){if (!vis[i]){vis[i] = true;dfs(层数+1, 其他参数);vis[i] = false;} }
}
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;
// dfsvoid 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 [USACO 1.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. 剪枝
- 可行性剪枝：对当前状态进行检查，如果当前条件不合法就不再继续，直接返回
- 搜索顺序剪枝：搜索树有多个层次和分支，不同的搜索顺序会产生不同的搜索树形态，复杂度也相差很大
- 最优性剪枝：在最优化问题的搜索过程中，如果当前花费的代价已超过前面搜索到的最优解，那么本次搜索就没有继续进行下去的意义，直接退出
- 排除等效冗余：如果沿当前节点搜索它的不同分支，最后的结果是一样的，那么只搜索一个分支就够了
- 记忆化搜索：在递归的过程中，有许多分支被反复计算，会大大降低算法的执行效率。用记忆化搜索，将已经计算出来的结果保存起来，以后需要用到时直接取出结果，避免重复运算，从而提高了算法的效率。记忆化搜索主要应用于动态规划