DFS三大经典问题
题目：
从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。 输入格式 输入一个整数 n。 输出格式 每行输出一种方案。 同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。 对于没有选任何数的方案，输出空行。 本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。 数据范围 1≤n≤15 输入样例： 3 输出样例： 3 2 2 3 1 1 3 1 2 1 2 3
分析：
递归实现指数型枚举： 所实现的功能就是，面对当前数的时候，做出了两种选择，选或不选。 而且，我们是从前往后来的，具有顺序性（升序筛选），所得的序列都是递增的。 选和不选，当前数都已经走过了，不会重复第二次面临选择的情况
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> v;
void dfs(int u)
{
if (u > n)
{
for (auto it : v)
cout << it << ' ';
cout << endl;
return;
}
dfs(u + 1);
v.push_back(u);
dfs(u + 1);
v.pop_back();
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
题目：
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。 输入格式 两个整数 n,m ,在同一行用空格隔开。 输出格式 按照从小到大的顺序输出所有方案，每行 1 个。 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。 数据范围 n>0 , 0≤m≤n , n+(n−m)≤25 输入样例： 5 3 输出样例： 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 思考题：如果要求使用非递归方法，该怎么做呢？
分析：
这个题，和上个题差距不大，只是多了一个长度限制。 不过，我们可以在传参的时候，在搜索状态空间的时候，多加一个状态，就是start，起始位置。
代码1：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> v;
void dfs(int u)
{
if (u > n)
{
if (v.size() != k) return;
for (auto it : v)
cout << it << ' ';
cout << endl;
return;
}
v.push_back(u);
dfs(u + 1);
v.pop_back();
dfs(u + 1);
}
int main()
{
cin >> n >> k;
dfs(1);
return 0;
}
代码2：
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> v;
void dfs(int u, int start)
{
if (u == k)
{
for (int i = 0; i < v.size(); i ++ )
cout << v[i] << " " ;
cout << endl;
return;
}
for (int i = start + 1; i <= n; i ++ )
{
v.push_back(i);
dfs(u + 1, i);
v.pop_back();
}
}
int main()
{
cin >> n >> k;
dfs(0, 0);
return 0;
}
题目：
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。 输入格式 一个整数 n。 输出格式 按照从小到大的顺序输出所有方案，每行 1 个。 首先，同一行相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。 数据范围 1≤n≤9 输入样例： 3 输出样例： 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
分析：
递归实现排列型枚举
当前数选过后，对于本递归搜索子树来说，不需要在此使用，但是对于其它子树来说，却需要重新使用。
代码：
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> v;
bool st[10];
void dfs(int u)
{
if (u == n)
{
for (int x : v)
cout << x << ' ';
cout << endl;
return;
}
for (int i = 1; i <= n; i ++ )
if (!st[i])
{
st[i] = true;
v.push_back(i);
dfs(u + 1);
v.pop_back();
st[i] = false;
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
DFS
DFS大致可以分为两种，一种内部搜索，另一种为外部搜索。
内部搜索，就像是在期盼内部搜索，寻找一条通路、或者搜索有多少个格子之类的，它在格子内部搜索，而且搜索过后，当前各点的状态是不会再发生变化的。
外部搜索，一般为方案数，需要棋盘自身的状态发生变化，每一个格点都有可能发生变化，从而会对全局产生影响。这个时
候，为了解决一个格点对应多状态的情况，需要恢复现场的操作。
（1）：分排列型枚举（先后顺序对结果有影响）、组合型枚举（对先后顺序没影响，如集合元素）
如果是排列型枚举：
如果是组合型枚举：可以在dfs内，加一个start，表示从第几个数开始搜索
外部搜索：
题目：
n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。 1_597ec77c49-8-queens.png 现在给定整数 n，请你输出所有的满足条件的棋子摆法。 输入格式 共一行，包含整数 n。 输出格式 每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。 其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。 每个方案输出完成后，输出一个空行。 注意：行末不能有多余空格。 输出方案的顺序任意，只要不重复且没有遗漏即可。 数据范围 1≤n≤9 输入样例： 4 输出样例： .Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..
代码：
#include <cstdio>
using namespace std;
const int N = 10;
int n, k;
char g[N][N];
int col[N], dg[N], udg[N];
void dfs(int u)
{
if (u == n)//当u=n的时候，说明前面从0到n-1这n行都排列好了，那就可以输出方案了
{
for (int i = 0; i < n; i ++ ) printf("%s
", g[i]);
puts("");
return;
}
for (int i = 0; i < n; i ++ )
if (!col[i] && !dg[i + u] && !udg[u - i + n]) //如果当前行，列，两个斜线都没有皇后
{
col[i] = dg[i + u] = udg[u - i + n] = true;
g[u][i] = 'Q';
dfs(u + 1);
//恢复现场
g[u][i] = '.';
col[i] = dg[i + u] = udg[u - i + n] = false;
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}
题目：
棋盘问题 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 109089 Accepted: 49235 Description 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 Output 对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。 Sample Input 2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1 Sample Output 2 1
分析：
和前面的八皇后问题一婶的。甚至更简单了。
代码：
#include <cstdio>
using namespace std;
const int N = 10;
int n, k;
char g[N][N];
bool col[N];
int ans;
void dfs(int u, int cnt)
{
if (u > n) return;//已经搜了n层，结束了
if (cnt == k)
{
ans ++;
return;
}
//不在这一层选，直接进入下一层
dfs(u + 1, cnt);
for (int i = 0; i < n; i ++ )//枚举u这一行的每一列
if (!col[i] && g[u][i] == '#')
{
col[i] = true;
dfs(u + 1, cnt + 1);
col[i] = false;
}
}
int main()
{
while (scanf("%d%d", &n, &k), ~n || ~k)
{
for (int i = 0; i < n; i ++ )
scanf("%s", g[i]);
for (int i = 0; i <= n; i ++ ) col[i] = 0;
ans = 0;
dfs(0, 0);
printf("%d
", ans);
}
}
BFS
BFS可以在入队的时候判重 ，dijkstra可以在出队的时候判重，A*不能判重
A*算法要保证有解才可以用，不然搜索空间可能会比直接用BFS还要大呢。
模板题：844. 走迷宫
题目：
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。 最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。 请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。 数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。 输入格式 第一行包含两个整数 n 和 m。 接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。 输出格式 输出一个整数，表示从左上角移动至右下角的最少移动次数。 数据范围 1≤n,m≤100 输入样例： 5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 输出样例： 8
分析：
BFS搜索： 所有BFS问题要保证两点：单调性、两段性
每次将队头取出，将可达状态全部拓展、并将产生的新的状态插入队列，等待更新
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 110;
int n,m ;
int g[N][N];
int dist[N][N];
void bfs()
{
memset(dist, -1, sizeof dist);
dist[1][1] = 0;
queue<PII> q;
q.push({1, 1});
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (q.size())
{
PII t = q.front();
q.pop();
// printf("%d %d
", t.x, t.y);
for (int i = 0; i < 4; i ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x <= 0 || x > n || y <= 0 || y > m) continue;
if (dist[x][y] != -1) continue;
if (g[x][y]) continue;
// printf("%d %d
", x, y);
dist[x][y] = dist[t.x][t.y] + 1;
q.push({x, y});
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &g[i][j]);
bfs();
printf("%d
", dist[n][m]);
return 0;
}
广搜显威题目：
题目：
在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。 例如： 1 2 3 x 4 6 7 5 8 在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。 我们的目的是通过交换，使得网格变为如下排列（称为正确排列）： 1 2 3 4 5 6 7 8 x 例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。 交换过程如下： 1 2 3 1 2 3 1 2 3 1 2 3 x 4 6 4 x 6 4 5 6 4 5 6 7 5 8 7 5 8 7 x 8 7 8 x 现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。 输入格式 输入占一行，将 3×3 的初始网格描绘出来。 例如，如果初始网格如下所示： 1 2 3 x 4 6 7 5 8 则输入为：1 2 3 x 4 6 7 5 8 输出格式 输出占一行，包含一个整数，表示最少交换次数。 如果不存在解决方案，则输出 −1。 输入样例： 2 3 4 1 5 x 7 6 8 输出样例 19
分析：
我的想法就是将x位置的数进行四个方向的交换
如果已经出现过这个状态，就continue，如果没有就加入到队列中，
所有状态也就是9！个，不多。每次查找x的位置，然后进行转换
和那个魔板【博客第二题】那题很像.
代码：（这个题以前的时候搁浅了好久，这次自己想，自己写，给写出来了，鸣炮，奏乐~~~）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
char g[3][3];
unordered_map<string, int> dist;
void set(string s)
{
for (int i = 0, t = 0; i < 3; i ++ )
for (int j = 0; j < 3; j ++ )
g[i][j] = s[t ++ ];
// cout << g[0][0] << g[0][1] << g[0][2] << endl;
// cout << g[1] << endl;
// cout << g[2] << endl;
// for (int i = 0; i < 3; i ++ )
// {
// for (int j = 0; j < 3; j ++ )
// printf("%c", g[i][j]);
// puts("");
// }
}
string get()
{
string s;
for (int i = 0, t = 0; i < 3; i ++ )
for (int j = 0; j < 3; j ++ )
s += g[i][j];
// cout << s << endl;
return s;
}
string Up(string s, int x, int y)
{
set(s);
swap(g[x][y], g[x - 1][y]);
return get();
}
string Right(string s, int x, int y)
{
set(s);
swap(g[x][y], g[x][y + 1]);
return get();
}
string Down(string s, int x, int y)
{
set(s);
swap(g[x][y], g[x + 1][y]);
return get();
}
string Left(string s, int x, int y)
{
set(s);
swap(g[x][y], g[x][y - 1]);
return get();
}
int bfs(string start, string end)
{
if (start == end) return 0;
queue<string> q;
q.push(start);
dist[start] = 0;
// int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (q.size())
{
string t = q.front();
q.pop();
int x, y;
for (int i = 0; i < t.size(); i ++ )
if (t[i] == 'x') x = i / 3, y = i % 3;
//四个操作没问题，检查过了
string m[4];
if (x > 0) m[0] = Up(t, x, y);
if (y < 2) m[1] = Right(t, x, y);
if (x < 2) m[2] = Down(t, x, y);
if (y > 0) m[3] = Left(t, x, y);
// puts("--------------");
// for (int i = 0; i < 4; i ++ ) cout << m[i] << endl;
// puts("[------------]");
for (int i = 0; i < 4; i ++ )
if (!dist.count(m[i]))
{
dist[m[i]] = dist[t] + 1;
q.push(m[i]);
if (m[i] == end) return dist[m[i]];
}
}
return -1;
}
int main()
{
string start, end;
end = "12345678x";
for (int i = 1; i <= 9; i ++ )
{
int c; scanf("%c ", &c);
start += c;
}
// set(start);
// get();
printf("%d
", bfs(start, end));
// cout << s << endl;
return 0;
}