回溯

C 中回溯的知识，是和深搜相关的。深搜中就有回溯。这儿有6道题目等你挑战！喜欢的小伙伴可以点个赞哦。

回溯

• 4.全排列输出
  • 题目：输入正整数N，输出由1到N这N个数(N<=7)的所有排列，每行一个排列，数与数之间有一个空格，两个排列中，第一个数小的优先输出，第一个数相同，比较第二个数，后面以此类推。
  • 输入输出描述：输入正数N，输出所有全排列。
  • 样例： 输入： 3 输出： 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
  • 思路：还是回溯经典的代码，如果循环到了第n+1层，输出，return.如果没有被标记过，标记，递归，回溯，取消标记。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int mark[10]; int a[11]; int n; void dfs(int dep) { if(dep == n + 1) //循环到了第n+1层循环 { for (int i = 1;i <= n;i++) cout << a[i] << " "; //输出 cout << endl; return ; } for (int i=1;i <= n;i++) { if (!mark[i]) { mark[i] = 1; //标记 a[dep] = i; //把i赋值给a数组的第dep个数 dfs(dep + 1); //递归 mark[i] = 0; //取消标记 } } } int main() { cin >> n; dfs(1); return 0; }
• 5.奇怪的机器人
  • 题目：小明有一台机器人，它会在一个n*n的棋盘上面走，最后返回有多少条路可以从起点走到终点。 有一天，小明闲着没事，便在棋盘上面放了若干个棋子，让机器人去走，但是道路数量太多了，小明不确定机器人算得对不对，需要你写个代码帮帮他。
  • 输入输出描述： 输入： 第一行，输入一个整数n——表示棋盘的行和列 接下来输入n行，每行n个字符——表示整个棋盘（只包含'.'和'#'，'.'表示空地，'#'表示棋子） 第n+2行，输入两个整数——表示起点的行和列 第n+3行，输入两个整数——表示终点的行和列 输出： The chessboard has ANS paths. 注：ANS表示答案，如答案为10时输出： The chessboard has 10 paths.
  • 样例： 输入： 6 ...... ...... ...... ...... ...... ...... 1 1 6 6 输出： The chessboard has 1262816 paths.
  • 思路：这题要使用深搜，深搜是有回溯的，深搜的代码都差不多，不过要注意下标，样例的下标是1，不过输入时下标是0，最后还要注意只要一个个字符串输入。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int n,vis[10][10],sx,sy,ex,ey,ans; int nt[5][2] = {{-1,0},{0,1},{1,0},{0,-1}}; char a[10][10]; void dfs(int x,int y) //深搜 { if (x == ex && y == ey) //如果到了终点 答案加一 { ans++; return ; } for (int i = 0;i < 4;i++) { int xx = x + nt[i][0]; //记录下一个位置在哪里 int yy = y + nt[i][1]; if (xx >= 0 && xx < n && yy >= 0 && yy < n && vis[xx][yy] == 0 && a[xx][yy] == '.') { vis[xx][yy] = 1; //进行回溯 dfs(xx,yy); vis[xx][yy] = 0; } } } int main() { cin >> n; for (int i = 0;i < n;i++) { scanf("%s",a[i]); } cin >> sx >> sy >> ex >> ey; sx--;sy--;ex--;ey--; //下标统一 vis[sx][sy] = 1; dfs(sx,sy); //深搜 printf("The chessboard has %d paths.",ans); return 0; }
• 6.二叉树遍历加强版
  • 题目：二叉树的每个结点包含一个大写字母，且两两不同。 给出二叉树的前序遍历和中序遍历，求后序遍历。
  • 输入输出描述： 输入： 第一行给出一个字符串表示前序遍历。 第二行给出一个字符串表示中序遍历。 遍历结果只由大写字母组成，非空，且长度不超过26。 输出：输出后序遍历的结果。
  • 样例1： 输入： DBACEGF ABCDEFG 输出： ACBFGED 样例2： 输入： BCAD CBAD 输出： CDAB
  • 思路：用一个函数计算，计算完后在遍历别的点。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 1010; char a[N]; char b[N]; vector<char> ans; void dfs(int l1,int r1,int l2,int r2) { if (l1 > r1 || l2 > r2) return ; int p = -1; for (int i = l2;i <= r2;i++) { if (b[i] == a[l1]) //判断是否一样 { p = i; break; } } int len = p - l2; //获取长度 dfs(l1+1,l1+len,l2,l2+len-1); dfs(l1+len+1,r1,p+1,r2); ans.push_back(a[l1]); } int main() { scanf("%s%s",a,b); int n = strlen(a); dfs(0,n-1,0,n-1); for (int i = 0;i < n;i++) { cout << ans[i]; } return 0; }
• 3.N皇后问题
  • 题目：在8*8国际象棋盘上，放置8个皇后，使得任意两个皇后都不会互相攻击，一共有多少种摆法？这就是著名的8皇后问题。 现在我们来尝试，在N*N的棋盘上，放置N个皇后，使得它们不会互相攻击。 皇后的走子规则是，沿着横、竖、两条对角线方向可以走任意步数。
  • 输入输出描述：输入1个整数N，输出一个整数,表示N皇后的不同解答个数。
  • 样例：输入：8 输出：92
  • 思路：定义一个变量row，第row行放一个皇后，N行就可以放N个皇后，可以用回溯来解答。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int lie[12],xie1[100],xie2[100]; //列，斜线1，斜线2 int n,ret; void dfs(int row) { if (row == n + 1) { ret++; return ; } //第row行选一列放皇后 for (int col = 1;col <= n;col++) { if(lie[col]==0&&xie1[row+col]==0&&xie2[row-col+10] ==0) { lie[col] = 1; xie1[row+col] = 1; xie2[row-col+10] = 1; dfs(row + 1); lie[col] = 0; xie1[row+col] = 0; xie2[row-col+10] = 0; //回溯 } } } int main() { scanf("%d",&n); dfs(1); printf("%d",ret); return 0; }
• 2.造素数
  • 题目：现在给你n个数，你需要从中选出m个数，使得这m个数的和为素数，求出可选的方案数。
  • 输入输出描述： 输入： 第一行两个整数n和m。 第二行n个整数，表示可选的数字。 输出： 输出有多少种方案可以使得选出的数之后为素数。
  • 样例1： 输入： 3 2 1 2 3 输出： 2 样例2： 输入： 3 1 2 2 2 输出： 3
  • 思路：这题和第一题类似，我们还是可以用函数来解答，首先用一个变量表示选了几个数，一个变量表示循环了几层，再定义一个函数，用来判断是否为素数。如果循环了n+1层并且选了m个数，就可以开始判断素数，如果是，答案加一。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int n,m,a[25],b[25],ret; bool check(int num) //判断是否为素数 { if (num == 1) return false; for (int i = 2;i * i<=num;i++) { if (num % i == 0) return false; } return true; } void dfs(int cnt,int dep) //cnt表示选了几个数 dep表示循环了几层 { if (dep == n + 1) //如果循环了 n+1 层 { if (cnt == m) //如果选了 m 个数 { int sum = 0; for (int i = 0;i < cnt;i++) sum += b[i]; //求这m个数的和 if (check(sum)) ret++; //判断是否为素数 如果是 则答案加一 } return ; } b[cnt] = a[dep]; //b数组记录选了哪些数 dfs(cnt+1,dep+1); dfs(cnt,dep+1); } int main() { scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) { scanf("%d",&a[i]); } dfs(0,1); printf("%d\n",ret); return 0; }
• 1.排队
  • 题目：小红是一名幼儿园的老师，她现在要带领小朋友们去做操了，做操之前需要给小朋友们排个队伍，这个问题总是让她感到为难， 因为小朋友们都喜欢和自己的玩伴排在一起。请你帮帮小红排队，使得跟玩伴在一起的小朋友对数最多。
  • 输入输出描述： 输入： 第一行两个整数n和m，n表示小朋友的个数，m表示玩伴的对数 接下来m行，每行两个整数a、b，表示编号为a的小朋友和编号为b的小朋友是玩伴。 输入数据中保证不会出现重复的玩伴对数，即（2,3）出现这不会再出现（2,3）和(3,2) 输出： 输出两行，第一行一个整数表示能排在一起的最多伙伴对数。 第二行为排队的方法，如果有多种可能，输出字典序最小的。
  • 样例： 输入： 3 2 2 1 1 3 输出： 2 2 1 3
  • 思路：如果变量枚举到了第n个循环，进行循环操作，退出。不是的话就for循环，如果数字没有标记过，就标记，将第dep层的数字赋值成i，递归，再取消标记。最后输出答案。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int n,m,a[12],mark[12],ret,ans[12],isfriend[12][12]; //递归枚举n个循环 void dfs(int dep)//dep表示当前是第几层循环 { if (dep == n + 1) { int cnt = 0; for (int i = 2;i <= n;i++) cnt += isfriend[a[i]][a[i-1]]; if (cnt > ret) { ret = cnt; for (int i = 1;i <= n;i++) ans[i] = a[i]; } return ; } for (int i = 1;i <= n;i++) { if (!mark[i])//第dep层选择了i这个数字 { mark[i] = 1; a[dep] = i;//将第dep层的数字赋值成i dfs(dep+1); mark[i] = 0; } } } int main() { scanf("%d%d",&n,&m); for (int i = 1;i <= m;i++) { int x,y; scanf("%d%d",&x,&y); isfriend[x][y] = isfriend[y][x] = 1; } dfs(1); printf("%d\n",ret); for (int i = 1;i <= n;i++) printf("%d ",ans[i]); return 0; }