深度优先搜索常用于解决需要给出所有方案的问题，因为它的搜索顺序就是能够得到一个完整的搜索路径（方案）后回退再去搜索其它的方案。
由于要求所有排列的方案，可以每次从 1.. n 1..n 1..n里拿一个数字，然后记录一下这个数拿过了，再递归地搜索下一个数字，当所有数字都取完之后，就得到了一种方案，将这种方案输出，回退之后去搜下一个方案。
“回退之后去搜下一个方案”，其实就是在每层DFS的时候遍历一下所有的允许使用的数字，作为下一个位置的数字。需要注意的是在进入下一层DFS之前要把这个数放进 p a t h path path里去，并记录一下这个数用过了，然后在回退之后还要把 p a t h path path末尾加入的这个数删掉，并记录一下这个数现在是没使用的状态。
基于这个思想，实现的代码如下：
#include <iostream>
#include <vector>
using namespace std;
const int N = 10;
int n;
vector<int> path;
bool st[N];
void dfs() {
if (path.size() == n) {
for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';
cout << endl;
return ;
}
for (int i = 1; i <= n; i ++ ) {
if (!st[i]) {
path.push_back(i);
st[i] = true;
dfs();
path.pop_back();
st[i] = false;
}
}
}
int main() {
cin >> n;
dfs();
return 0;
}
这里是用一个vector存了
p
a
t
h
path
path，然后在装满（装够
n
n
n个数）的时候把整个方案输出出来。如果用数组的话，可以将DFS进行到了哪一层（数组里放了多少数字）维护一下，可以放在参数里，也可以直接在全局维护。另外，这里是用一个bool类型的st数组维护了每个数字有没有被使用过，由于数的范围很小，还不到32位int，所以可以直接用一个int值来代替st，也就进行了二进制优化。
另外，将这个int值作为参数在DFS中进行值传递，就不会在下一层里对它有修改了，这样写起来也方便，这里的语义是表示一种“状态”。
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int path[N];
int n;
// 当前放置u位置的数字，目前所有数字使用状态是state
void dfs(int u, int state) {
if (u == n) {
for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';
cout << endl;
return ;
}
for (int i = 1; i <= n; i ++ ) {
if (state & (1 << i)) continue;
path[u] = i;
dfs(u + 1, state + (1 << i));
}
}
int main() {
cin >> n;
// 从第0位置的数开始，状态一开始是全0，所有数字没使用
dfs(0, 0);
return 0;
}
这个问题里，由于限制了每行、每列、每个对角线上都只能有一个'Q'，所以可以把一些条件融入到搜索顺序中去。比如看到第一个条件“每行只能有一个'Q'”，所以可以DFS的每层搜索这一行的'Q'应该放在哪一列，然后再保证这一列没有放置过（用col数组检查），保证这个位置所在的主正反对角线（用dg和udg数组检查）没有放置过。
如何知道一个位置是在哪个正反对角线上的？可以发现正反对角线上的元素
(
x
,
y
)
(x, y)
(x,y)的特征，分别是
x
+
y
x + y
x+y等于一个固定值，以及
x
−
y
x - y
x−y等于一个固定值，所以可以开
2
∗
n
2 * n
2∗n的一维数组dg和udg记录一下。
#include <iostream>
using namespace std;
const int N = 12;
char g[N][N];
bool col[N], dg[2 * N], udg[2 * N];
int n;
// 当前搜索u号行
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < n; j ++ )
cout << g[i][j];
cout << endl;
}
cout << endl;
return ;
}
for (int j = 0; j < n; j ++ ) {
if (col[j] || dg[u + j] || udg[u - j + n]) continue;
col[j] = dg[u + j] = udg[u - j + n] = true;
g[u][j] = 'Q';
dfs(u + 1);
col[j] = dg[u + j] = udg[u - j + n] = false;
g[u][j] = '.';
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}
广度优先搜索每次扩展当前结点的所有结点，所以需要一个栈来维护要扩展的结点。由于广度优先搜索每次都是把所有能到的下一步搜完，所以能够得到最短 p a t h path path的解，所以一些不带权求最短路径的问题也可以直接用BFS解决。
注意，在扩展结点的某个下一结点（也就是把这个下一结点加入到队列）的时候，要保证这个结点是没被扩展过的，否则队列里就有重复结点了，就会出现重复访问了。
这个就是一个不带边权的最短路问题，直接BFS搜一下就行了，遇到墙或者已经扩展过的点就不用扩展了，核心在与到扩展的点的最短距离，等于到当前点的最短距离+1，也就是dist[a][b] = dist[x][y] + 1。
注意这里用dist中某个点值为-1表示这个点没有访问过，注意边界：到
(
0
,
0
)
(0, 0)
(0,0)位置自己的距离是0。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
// 存图
int g[N][N];
// 四个方向
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
// (0, 0)到每个点的距离
int dist[N][N];
int main() {
memset(dist, -1, sizeof dist);
dist[0][0] = 0;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> g[i][j];
// BFS
queue<PII> q;
q.push({0, 0});
while (q.size()) {
auto& t = q.front();
q.pop();
int x = t.first, y = t.second;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 1 || dist[a][b] != -1)
continue;
dist[a][b] = dist[x][y] + 1;
q.push({a, b});
}
}
cout << dist[n - 1][m - 1] << endl;
return 0;
}
这个问题就是把整个九宫格的局面当成一个节点，给定一个局面，就能够知道如何转移到其它局面，以及给出了目标局面，要求最短转移是多少步：
所以要想个方法来记录局面，可以从上到下从左到右记录到一个字符串里（就相当于二维字符数组展品成了一维），由于知道行数为 3 3 3列数为 3 3 3，可以很方便的对两者的下标进行转换。
另外要记录到每个结点的距离，由于这里的结点是局面（字符串），不能像上一个题一样开个数组记录了，所以可以用哈希表来记录。
其它的和上一题没有本质区别，都是求无权最短路的问题，直接BFS。
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string state) {
queue<string> q;
// 记录路径长度
unordered_map<string, int> d;
// 起始状态放进去
q.push(state);
d[state] = 0;
// 四个方向
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
// 终止状态，搜索的目标状态
string end = "12345678x";
// BFS搜索过程
while (q.size()) {
string t = q.front();
q.pop();
// 如果能到目标状态就返回距离
if (t == end)
return d[t];
// 因为一会要直接在t上交换，所以这里记录一下到t的距离
// 也可以直接把t这个当前状态复制一份
int dist = d[t];
// 找到x的下标，可以变换成(x, y)的二维形式
int k = t.find('x');
int x = k / 3, y = k % 3;
// 四个方向搜
for (int i = 0; i < 4; i ++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 3 || b < 0 || b >= 3)
continue;
// 做交换
swap(t[a * 3 + b], t[k]);
// 如果交换后的状态没扩展过
if (!d.count(t)) {
// 就扩展一下，还要记录它扩展过了（写入距离）
d[t] = dist + 1;
q.push(t);
}
// 交换回来，以恢复t
swap(t[a * 3 + b], t[k]);
}
}
// 到这说明无法搜到end状态
return -1;
}
int main() {
char s;
string state;
// 读入开始局面，以字符串形式存储
for (int i = 0; i < 9; i ++) {
cin >> s;
state += s;
}
// 这里把BFS封装起来了，不过没有递归不写到函数里也行
cout << bfs(state) << endl;
return 0;
}