A - 组合的输出

  1. #include <cstdio>
  2. #include <cstring>
  3. using namespace std;
  4. const int MAXN = 25 + 1;
  5. int n, r;
  6. int a[MAXN];  //数组a保存在“棋盘”上的"棋子"
  8. void dfs(int k) {
  9.     for (int i = a[k - 1] + 1; i <= n; i++) {
  10.         a[k] = i;
  11.         if (k == r) {
  12.             for (int j = 1; j <= r; j++) printf("%3d", a[j]);
  13.             printf("\n");
  14.         }
  15.         else {
  16.             dfs(k + 1);
  17.         }
  18.     }
  19. }
  20. int main() {
  21.     while (~scanf("%d%d", &n, &r)) {
  22.         memset(a, 0, sizeof(a));
  23.         dfs(1);
  24.     }
  25.     return 0;
  26. }

B - 自然数拆分

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. const int MAXN = 30;
  5. int n,sum = 0;
  6. int a[MAXN];  
  8. void dfs(int k) {
  9.     for (int i = a[k-1]; i <= n; i++) {  //每次从上一个填入的数字开始
  10.         if (i == n) continue;
  11.         sum -= a[k];  //虽然我用了回溯，但是这种用法不是很优雅
  12.         a[k] = i;
  13.         sum += a[k];
  15.         if (sum == n) {
  16.             cout << n << '=';
  17.             for (int i = 1; i < k; i++) {
  18.                 cout << a[i] << '+';
  19.             }
  20.             cout << a[k] << endl;
  21.             sum -= i;
  22.             a[k] = 0;
  23.         }
  24.         else if (sum < n) {
  25.             dfs(k + 1);
  26.         }
  27.         else {
  28.             sum = sum - i;
  29.             a[k] = 0;
  30.         }
  31.     }
  32. }
  33. int main() {
  34.     cin >> n;
  35.     memset(a, 0, sizeof(a));
  36.     sum = 0;
  37.     a[0] = 1;  //注意边界
  38.     dfs(1);
  39.     return 0;
  40. }

优雅的改进版

  1. void dfs(int k) {
  2.     for (int i = a[k-1]; i <= n - sum; i++) {  //n-sum避免 sum > n的情况，该情况要回溯“两次”
  3.         if (i == n) continue;
  4.         a[k] = i;
  5.         sum += a[k];
  7.         if (sum == n) {
  8.             cout << n << '=';
  9.             for (int i = 1; i < k; i++) {
  10.                 cout << a[i] << '+';
  11.             }
  12.             cout << a[k] << endl;
  13.         }
  14.         else {
  15.             dfs(k + 1);
  16.         }
  17.         sum -= i;
  18.     }
  19. }

C - LETTERS（这起得什么无意义的名字）

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. const int MAXN = 100;
  6. int m, n;
  7. string s;
  8. char a[MAXN][21] = {0};
  9. bool vis[MAXN][21] = { 0 };
  10. int ans = 0;
  12. void dfs(int i, int j) {
  13.     if (vis[i][j] == 1 || i < 1 || i > m || j < 1 || j > n) return;  //出界或是已经访问过
  15.     char c = a[i][j];
  16.     if (s.find(c) != EOF) return;  //每种字符只能访问一次
  17.     vis[i][j] = 1;
  18.     s += c;
  19.     /*cout << s << endl;*/
  20.     if (s.size() > ans) { ans = s.size(); /*cout << s << ' ' << ans << endl;*/ }
  21.     int pos = s.size() - 1;  
  23.     dfs(i - 1, j);
  24.     dfs(i + 1, j);
  25.     dfs(i, j - 1);
  26.     dfs(i, j + 1);
  28.     s.erase(pos);  //回溯,把/**/中的输出添加上可以发现有回溯和没有回溯的区别
  29.     vis[i][j] = 0;
  31.     return;
  32. }
  34. int main() {
  35.     while (~scanf_s("%d%d", &m, &n)) {
  36.         s.clear();
  37.         ans = 0;
  38.         memset(a, 0, sizeof(a));
  39.         memset(vis, 0, sizeof(vis));
  40.         for (int i = 1; i <= m; i++) {
  41.             for (int j = 1; j <= n; j++) {
  42.                 cin >> a[i][j];
  43.             }
  44.         }
  45.         dfs(1, 1);
  46.         cout << ans << endl;
  47.     }
  48.     return 0;
  49. }

D-n皇后问题

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. const int MAXN = 21;
  6. int n;
  7. int ans = 0;
  8. int a[MAXN] = { 0 };
  9. void showMap() {
  10.     for (int i = 1; i <= n; i++) {
  11.         for (int j = 1; j <= n; j++) {
  12.             if (j == a[i]) cout << '1' << ' ';
  13.             else cout << '0' << ' ';
  14.         }
  15.         cout << endl;
  16.     }
  17.     cout << endl;
  18. }
  19. bool check(int x, int y) {
  20.     for (int i = 1; i < x; i++) {
  21.         if (a[i] == y) return false;
  22.         if (i + a[i] == x + y) return false;
  23.         if (i - a[i] == x - y) return false;
  24.     }
  25.     return true;
  26. }
  27. void dfs(int row) {
  28.     if (row == n + 1) {
  29.         showMap();
  30.         ans++;
  31.         return;
  32.     }
  33.     for (int i = 1; i <= n; i++) {
  34.         if (check(row, i)) {
  35.             a[row] = i;
  36.             dfs(row + 1);
  37.             a[row] = 0;  //回溯
  38.         }
  39.     }
  40. }
  41. int main() {
  42.     cin >> n;
  43.     dfs(1);
  44.     cout << ans;
  45.     return 0;
  46. }

八皇后（改）

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5. const int n = 8;
  6. int ans = 0, pos = 1;
  7. int a[n + 1] = { 0 };
  8. int order[93] = { 0 };
  10. void func() {
  11.     for (int i = 1; i <= 8; i++) {
  12.         cout << a[i];
  13.     }
  14.     cout << endl;
  15. }
  16. bool check(int x, int y) {
  17.     for (int i = 1; i < x; i++) {
  18.         if (a[i] == y) return false;
  19.         if (i + a[i] == x + y) return false;
  20.         if (i - a[i] == x - y) return false;
  21.     }
  22.     return true;
  23. }
  24. void dfs(int row) {
  25.     if (row == n + 1) {
  26.         ans++;
  27.         if (ans == order[pos]) {
  28.             pos++;
  29.             func();
  30.         }
  31.         return;
  32.     }
  33.     for (int i = 1; i <= n; i++) {
  34.         if (check(row, i)) {
  35.             a[row] = i;
  36.             dfs(row + 1);
  37.             a[row] = 0;  //回溯
  38.         }
  39.     }
  40. }
  41. int main() {
  42.     int num;
  43.     cin >> num;
  44.     for (int i = 1; i <= num; i++) {
  45.         cin >> order[i];
  46.     }
  47.     sort(order + 1, order + 1 + num);
  48.     dfs(1);
  49.     return 0;
  50. }

F - 迷宫（一）

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. const int MAXN = 21;
  6. char a[MAXN][11] = { 0 };
  7. bool vis[MAXN][11] = { 0 };
  8. int n, m, s1, s2, g1, g2;
  9. int flag = 0;
  11. void dfs(int x, int y) {
  12.     if (x == g1 && y == g2) { flag = 1; return; }
  13.     if (vis[x][y] == 1 || x < 1 || x > n || y < 1 || y > m) return;
  15.     vis[x][y] = 1;
  16.     dfs(x - 1, y);
  17.     dfs(x + 1, y);
  18.     dfs(x, y - 1);
  19.     dfs(x, y + 1);
  20.     vis[x][y] = 0;  //回溯
  21. }
  22. int main() {
  23.     cin >> n >> m;
  24.     for (int i = 1; i <= n; i++) {
  25.         for (int j = 1; j <= m; j++) {
  26.             cin >> a[i][j];
  27.             if (a[i][j] == 'S') { s1 = i; s2 = j; }  //保存入口坐标
  28.             if (a[i][j] == 'T') { g1 = i; g2 = j; }  //保存出口坐标
  29.             if (a[i][j] == '*') vis[i][j] = 1;  //墙壁不可通过
  30.         }
  31.     }
  32.     dfs(s1, s2);
  33.     if (flag) cout << "yes";
  34.     else cout << "no";
  36.     return 0;
  37. }

G - 迷宫（二）

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. const int MAXN = 21;
  6. char a[MAXN][11] = { 0 };
  7. bool vis[MAXN][11] = { 0 };
  8. int n, m, s1, s2, g1, g2;
  9. int ans = -1,cnt = 0;
  10. void dfs(int x, int y) {
  11.     if (x == g1 && y == g2) {
  12.         ans++;
  13.         if (cnt == 0) cnt = ans;
  14.         else cnt = cnt < ans ? cnt : ans;
  15.         ans--;  //回溯
  16.         return; 
  17.     }
  18.     if (vis[x][y] == 1 || x < 1 || x > n || y < 1 || y > m) return;
  19.     vis[x][y] = 1;
  20.     ans++;
  21.     dfs(x - 1, y);
  22.     dfs(x + 1, y);
  23.     dfs(x, y - 1);
  24.     dfs(x, y + 1);
  25.     vis[x][y] = 0;  //回溯
  26.     ans--;
  27. }
  28. int main() {
  29.     cin >> n >> m;
  30.     for (int i = 1; i <= n; i++) {
  31.         for (int j = 1; j <= m; j++) {
  32.             cin >> a[i][j];
  33.             if (a[i][j] == 'S') { s1 = i; s2 = j; }  //保存入口坐标
  34.             if (a[i][j] == 'T') { g1 = i; g2 = j; }  //保存出口坐标
  35.             if (a[i][j] == '*') vis[i][j] = 1;  //墙壁不可通过
  36.         }
  37.     }
  38.     dfs(s1, s2);
  39.     if (cnt) cout << cnt;
  40.     else cout << "-1";
  41.     return 0;
  42. }

H - 迷宫（三）

  1. #include <iostream>
  2. using namespace std;
  3. const int MAXN = 31;
  4. bool goal[MAXN][16] = { 0 };
  5. bool vis[MAXN][16] = { 0 };
  6. int n, m;
  7. int ans = -1,cnt = 0;
  8. void dfs(int x, int y) {
  9.     if (goal[x][y] == 1) {  //到达终点
  10.         ans++;
  11.         if (cnt == 0) cnt = ans;
  12.         else cnt = cnt < ans ? cnt : ans;
  13.         ans--;  //回溯
  14.         return; 
  15.     }
  16.     if (vis[x][y] == 1 || x < 1 || x > n || y < 1 || y > m) return;
  17.     vis[x][y] = 1;
  18.     ans++;
  19.     dfs(x - 1, y);
  20.     dfs(x + 1, y);
  21.     dfs(x, y - 1);
  22.     dfs(x, y + 1);
  23.     vis[x][y] = 0;  //回溯
  24.     ans--;
  25. }
  26. int main() {
  27.     char ch;
  28.     cin >> n >> m;
  29.     int x, y;
  30.     for (int i = 1; i <= n; i++) {
  31.         for (int j = 1; j <= m; j++) {
  32.             cin >> ch;
  33.             if (ch == '#') vis[i][j] = 1;  //墙壁不可通过
  34.             else if ((i == 1 || i == n || j == 1 || j == m) && ch == '.') { goal[i][j] = 1; }  //保存终点坐标
  35.             if (ch == '@') { x = i; y = j; }  //保存起点坐标
  36.         }
  37.     }
  38.     dfs(x, y);
  39.     if (cnt) cout << cnt;
  40.     else cout << "-1";
  41.     return 0;
  42. }

I - 棋盘问题（递归理解重点题）

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. const int MAXN = 9;
  6. int a[MAXN] = { 0 };
  7. char map[MAXN][MAXN] = { 0 };
  8. int n, k, ans;
  9. int num = 0;
  11. bool check(int x, int y) {
  12.     if (map[x][y] == '.') return false;
  13.     for (int i = 1; i < x; i++) {
  14.         if (a[i] == y) return false;
  15.     }
  16.     return true;
  17. }
  18. void dfs(int row) {
  19.     if (num == k) { ans++; return; }  //值得注意的点
  20.     if (row == n + 1) return;
  21.     for (int i = 1; i <= n; i++) {
  22.         if (check(row, i)) {
  23.             a[row] = i;
  24.             num++;
  25.             dfs(row + 1);  
  26.             a[row] = 0;
  27.             num--;
  28.         }
  29.     }
  30.     dfs(row + 1);  //本题的精髓:
  31. }
  32. int main() {
  33.     while (~scanf_s("%d%d", &n, &k)) {
  34.         if (n == -1 && k == -1) break;
  35.         /*init*/
  36.         memset(a, 0, sizeof(a));
  37.         memset(map, 0, sizeof(map));
  38.         ans = 0;
  39.         num = 0;
  40.         /*input*/
  41.         for (int i = 1; i <= n; i++) {
  42.             for (int j = 1; j <= n; j++) {
  43.                 cin >> map[i][j];
  44.             }
  45.         }
  46.         /*dfs*/
  47.         dfs(1);
  48.         /*output*/
  49.         cout << "ans = " << ans;
  50.     }
  51.     return 0;
  52. }

L - 马走日

  • 我的答案是正确答案的8倍，以下为修改版 ```cpp

    include

    include

    include

    using namespace std; const int MAXN = 6; int m, n; bool vis[MAXN][MAXN] = { 0 }; int step = 0, ans = 0; int dir1[8] = { 1,1,-1,-1,2,2,-2,-2 }; int dir2[8] = { 2,-2,2,-2,1,-1,1,-1 }; bool checkSteps(int x, int y) //判断每次搜索的方向是否合法 { if (vis[x][y] == true) //判断是否被走过了

    1.   return false;

    if (x >= n || x < 0 || y >= m || y < 0) //判断是否越界

    1.   return false;

    return true; } void dfs(int x,int y) { if (step == n * m - 1) { ans++; return; } for (int i = 0; i < 8; i++) {

    1.   if (!checkSteps(x + dir1[i], y + dir2[i])) continue;
    2.   step++;
    3.   vis[x][y] = 1;
    4.   dfs(x + dir1[i], y + dir2[i]);
    5.   step--;  //回溯
    6.   vis[x][y] = 0;

    } }

int main() { int t; cin >> t; for (int i = 1; i <= t; i++) { int x, y; cin >> n >> m >> x >> y; /init/ memset(vis, 0, sizeof(vis)); ans = 0; step = 0; /dfs/ dfs(x, y); cout << ans << endl; } return 0; } ```