DFS:
1.数字的全排列问题：
#include <iostream> using namespace std; const int N = 10; int n; int path[N]; bool st[N]; // 记录哪些点被用过了 void dfs(int u) { if (u == n) { // 递归到第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[u] = i; // 此层选择数字i st[i] = true; dfs(u + 1); st[i] = false; // 恢复现场 } } } int main() { cin >> n; dfs(0); return 0; }
2.n皇后问题
#include <iostream> using namespace std; const int N = 20; int n; char g[N][N]; bool col[N], dg[N], udg[N]; // dg:正对角线；udg:反对角线 void dfs(int u) // 第u行的皇后应该放到哪一列 { if (u == n+1) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << g[i][j]; } cout << endl; } cout << endl; return; // 别忘了返回！！！ } for (int i = 1; i <= n; i++) // 枚举列 { if (col[i] || dg[u + i] || udg[n - u + i]) {//这里是根据y=x+b和y=-x+b--->b=y-x和b=y+x得到的 //注意b=y-x可能为负，所以加上偏移量n得到b=n+y-x } else { g[u][i] = 'Q'; col[i] = dg[u + i] = udg[n - u + i] = true; dfs(u + 1); col[i] = dg[u + i] = udg[n - u + i] = false; g[u][i] = '.'; } } } int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { g[i][j] = '.'; } } dfs(1); return 0; }
#include <iostream> using namespace std; const int N = 20; int n; char g[N][N]; bool row[N], col[N], dg[N], udg[N]; // dg:正对角线；udg:反对角线 void dfs(int x, int y, int s) // 第x行，第y列，当前有s个皇后 { if (y == n) { y = 0, x++; // 出界，转到下一行第一个位置 } if (x == n) // 最后一行 { if (s == n) // 正好有n个皇后 { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << g[i][j]; } cout << endl; } cout << endl; } return; } // 不放皇后 dfs(x, y + 1, s); // 放皇后 if (!row[x] && !col[y] && !dg[x + y] && !udg[n + y - x]) { g[x][y] = 'Q'; row[x] = col[y] = dg[x + y] = udg[n + y - x] = true; dfs(x, y + 1, s + 1); // 恢复现场！！！！！ row[x] = col[y] = dg[x + y] = udg[n + y - x] = false; g[x][y] = '.'; } } int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = '.'; } } dfs(0, 0, 0); return 0; }
