问题 A: 皇后问题(递归)题目描述编写一个函数求解皇后问题在 n×nn \times nn×n 的方格棋盘上放置 nnn 个皇后要求每个皇后不同行、不同列、不同左右对角线。要求1、皇后的个数由用户输入其值不超过 202020输出所有的解。2、采用递归回溯的方法解决。输入输入一个整数 nnn代表棋盘的大小输出将计算出的彼此不受攻击的 nnn 个皇后的所有放置方案输出每种方案占一行。输入输出样例样例输入 #1复制4样例输出 #1复制2 4 1 3 3 1 4 2提示1、规定搜索时每行从左向右每列从上往下搜索2、尽量采用较优算法3、使用递归求解#includeiostream #includevector using namespace std; int n; const int N 1e5; vectorboolcol(N, false);//列 vectorbooldg1(N, false);//主对角线 vectorbooldg2(N, false);//副对角线 vectorvectorintans;//答案 vectorinttmp;//临时数组存放每次的答案 void print(vectorvectorinta) { for (auto arr : a) { for (int e : arr) cout e ; cout \n; } } //遍历每一行 void dfs(int u) { if (u n)//遍历完n行就存储当前的答案 { ans.push_back(tmp); return; } for (int i 0;i n;i) { if (col[i] false dg1[u - i n] false dg2[u i] false) { //标记访问 col[i] true;//行 //主对角线方向x-y为定值但可能为负数故加上n dg1[u - i n] true; //副对角线方向xy为定值 dg2[u i] true; tmp.push_back(i 1); dfs(u 1); //回溯 col[i] false; dg1[u - i n] false; dg2[u i] false; tmp.pop_back(); } } } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin n; dfs(0);//从第一行开始搜索 print(ans); return 0; }问题 B: 八皇后问题题目描述会下国际象棋的人都很清楚 皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8 个皇后放在棋盘有8×88 \times88×8 个方格 上 使它们谁也不能被吃掉这 就是著名的八皇后问题。 对于某个满足要求的八个皇后的摆放方法 定 义一个皇后串 a 与之对应 即ab1b2…b8a b1 b2 … b8ab1b2…b8 , 其中 bi 为相应摆法中第 i 行皇后所处的列数。已经知道八皇后问题一共有92 组解即 92 个不同的皇后串。给出一个数b , 要求输出第b 个串。串的比较是这样的 皇后串 x 置于皇后串 y 之前 当且仅当将 x 视为整数时比 y 小。输入第 1 行是测试数据的组数n , 后面跟着n 行输入。每组测试数据占 1 行 包含一个正整数b(1≤b≤92)(1 \leq b \leq 92)(1≤b≤92)输出输出有 n 行 每行输出对应一个输入。输出应是一个正整数 是对应于b 的皇后串。输入输出样例样例输入 #1复制2 1 92样例输出 #1复制15863724 84136275#includeiostream #includevector using namespace std; int n; const int N 1e5; vectorboolcol(N, false);//列 vectorbooldg1(N, false);//主对角线 vectorbooldg2(N, false);//副对角线 vectorvectorintans;//答案 vectorinttmp;//临时数组存放每次的答案 //遍历每一行 void dfs(int u) { if (u n)//遍历完n行就存储当前的答案 { ans.push_back(tmp); return; } for (int i 0;i n;i) { if (col[i] false dg1[u - i n] false dg2[u i] false) { //标记访问 col[i] true;//行 //主对角线方向x-y为定值但可能为负数故加上n dg1[u - i n] true; //副对角线方向xy为定值 dg2[u i] true; tmp.push_back(i 1); dfs(u 1); //回溯 col[i] false; dg1[u - i n] false; dg2[u i] false; tmp.pop_back(); } } } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); n 8; dfs(0);//从第一行开始搜索 int t; cin t; while (t--) { int x; cin x; if (x 1 x 92) { for (int e : ans[x - 1]) cout e; cout \n; } } return 0; }问题 E: 搜索基础之红与黑题目描述有一间长方形的房子地上铺了白色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上只能向相邻的黑色瓷砖移动。请写一个程序计算你总共能够到达多少块黑色的瓷砖。输入包括多个数据集合。每个数据集合的第一行是两个整数 WWW 和 HHH分别表示 xxx 方向和 yyy 方向瓷砖的数量。WWW 和 HHH都不超过 20。在接下来的 HHH 行中每行包括 WWW 个字符。每个字符表示一块瓷砖的颜色规则如下1.黑色的瓷砖2#白色的瓷砖3黑色的瓷砖并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。当在一行中读入的是两个零时表示输入结束。输出对每个数据集合分别输出一行显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。输入输出样例样例输入 #1复制6 9 ....#. .....# ...... ...... ...... ...... ...... #...# .#..#. 0 0样例输出 #1复制45#includeiostream #includevector #define int long long using namespace std; int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; int cnt 0; int n 1, m 1; //要加引用不然函数里面的改变不影响外层 void dfs(int x, int y, vectorvectorboolvis, vectorvectorcharg) { //先卡边界 if (x 0 || x n || y 0 || y m) return; if (vis[x][y] true) return; if (g[x][y] #) return; vis[x][y] true; cnt;//计数 for (int i 0;i 4;i) { int cx x dx[i]; int cy y dy[i]; if (cx 0 || cx n || cy 0 || cy m) continue; dfs(cx, cy, vis, g); } } signed main() { int sx 0; int sy 0; while (cin m n n ! 0 m ! 0) { vectorvectorboolvis(n, vectorbool(m, false)); vectorvectorcharg(n, vectorchar(m)); for (int i 0;i n;i) { for (int j 0;j m;j) { cin g[i][j]; if (g[i][j] ) { sx i; sy j; } } } dfs(sx, sy, vis, g); cout cnt endl; cnt 0; } return 0; }问题 F: 搜索基础之棋盘问题题目描述在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放 kkk 个棋子的所有可行的摆放方案 CCC。输入输入含有多组测试数据。每组数据的第一行是两个正整数 nnn kkk用一个空格隔开表示了将在一个 n×nn \times nn×n 的矩阵内描述棋盘以及摆放棋子的数目。0n≤80 \lt n \le 80n≤8 0k≤n0 \lt k \le n0k≤n当为-1 -1时表示输入结束。随后的 nnn 行描述了棋盘的形状每行有 nnn 个字符其中#表示棋盘区域.表示空白区域数据保证不出现多余的空白行或者空白列。输出对于每一组数据给出一行输出输出摆放的方案数目 CCC 数据保证 C231C \lt 2^{31}C231。输入输出样例样例输入 #1复制2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1样例输出 #1复制2 1#includeiostream #includevector using namespace std; int n, k; const int N 1e5; vectorboolcol(N, false); void dfs(int u, vectorvectorcharg, int cnt) { if (u k) { cnt; return; } for (int i 0;i n;i) { if (col[i] false g[u][i] #) { col[i] true; dfs(i 1, g, cnt); col[i] false; } } } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); while (cin n k n ! -1) { int cnt 0; vectorvectorcharg(n, vectorchar(n)); for (int i 0;i n;i) { for (int j 0;j n;j) cin g[i][j]; } dfs(0, g, cnt); cout cnt \n; } return 0; }问题 G: 小游戏题目描述你决定编写一个小游戏。游戏在一个分割成w× hw \times hw× h 个正方格子的矩形板上 进行。如图4- 2 所示每个正 方格子上可以有一张游戏卡片 当然也可以没有。当下面的情况满足时认为两个游戏卡片之间有一条路径相连路径只包含水平或者竖直的 直线段。路径不能穿过别的游戏卡片但是允许路径临时离开矩形板。下面是一个例子。这里在(1,3)( 1 ,3 )(1,3) 和(4,4)( 4,4 )(4,4)处的游戏卡片是可以相连的 而在(2,3)( 2 ,3 )(2,3) 和(3,4)( 3 , 4 )(3,4) 处的游戏卡片是不相连的 因为连接它们的每条路径都必须穿过别的游戏卡片。现在要在小游戏中判断是否存在一条满足题意的路径能连接给定的两个游戏卡片。输入输入包含多组数据。一个矩形板对应一组数据。每组数据的第一行包含两个整数 ww w和h(1 ≤w,h≤75)h (1 \leq w, h \leq 75)h(1 ≤w,h≤75) 分别表示矩形板的宽度和长度。下面的 hhh 行 每行包括 www 个字符 表示矩形板上的游戏卡片分布情况 。使用 X 表示某个地方有一个游戏卡片 使用空格表示某个地方没有游戏卡片。之后的若干行中每行包含 4 个整数x1,y1,x2(1≤x1,x2≤w,1≤y1,y2≤h)x1 , y1 ,x2 (1 \leq x1,x2 \leq w,1 \leq y1 , y2 \leq h )x1,y1,x2(1≤x1,x2≤w,1≤y1,y2≤h)。给出两个卡片在矩形板上的位置 注意 矩形板左上角的坐标是(1,1)(1 ,1 )(1,1) 。输入保证这两个游戏卡片所处的位置是不相同的。如果一行上有 4 个 0 , 表示这组测试数据的结束。如果一行上给出wh0w h 0wh0 那么表示所有的输入结束 。输出对每一个矩形板 输出一行 “ Board #n:Board\ \#n:Board #n:这里 n 是输入数据的编号。然后对每一组需要测试的游戏卡片输出一行 这一行的开头是 “ Pair m: 这里 m 是测试卡片的编号 对于每个矩形板 编号都从1 开始。接下来 如果可以相连 找到连接这两个卡片的所有路径中包 含线段数最少的路径 输出 “ k segments . 这里 k 是找到的最优路径中包含的线段的数目 如果不能相连 则输出 “ impossible. 。每组数据之后输出一个空行。输入输出样例样例输入 #1复制5 4 XXXXX X X XXX X XXX 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0 0 0样例输出 #1复制Board #1: Pair 1: 4 segments. Pair 2: 3 segments. Pair 3: impossible.提示如果出现输出超限的原因参考以下地图读入代码for(int i1; ih; i) { for(int j1; jw; j) { char ch getchar(); while(ch ! ch ! X) { ch getchar(); } if(chX) mp[i][j]1; } }如果出现时间超限的问题请考虑切换搜索方向。