问题 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、使用递归求解！
#include<iostream> #include<vector> using namespace std; int n; const int N = 1e5; vector<bool>col(N, false);//列 vector<bool>dg1(N, false);//主对角线 vector<bool>dg2(N, false);//副对角线 vector<vector<int>>ans;//答案 vector<int>tmp;//临时数组，存放每次的答案 void print(vector<vector<int>>a) { 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; //副对角线方向：x+y为定值 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 与之对应， 即a=b1b2…b8a = b1 b2 … b8a=b1b2…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#include<iostream> #include<vector> using namespace std; int n; const int N = 1e5; vector<bool>col(N, false);//列 vector<bool>dg1(N, false);//主对角线 vector<bool>dg2(N, false);//副对角线 vector<vector<int>>ans;//答案 vector<int>tmp;//临时数组，存放每次的答案 //遍历每一行 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; //副对角线方向：x+y为定值 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#include<iostream> #include<vector> #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, vector<vector<bool>>&vis, vector<vector<char>>&g) { //先卡边界 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) { vector<vector<bool>>vis(n, vector<bool>(m, false)); vector<vector<char>>g(n, vector<char>(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 的矩阵内描述棋盘，以及摆放棋子的数目。0<n≤80 \lt n \le 80<n≤8 0<k≤n0 \lt k \le n0<k≤n
当为-1 -1时表示输入结束。
随后的 nnn 行描述了棋盘的形状：每行有 nnn 个字符，其中#表示棋盘区域，.表示空白区域（数据保证不出现多余的空白行或者空白列）。
输出
对于每一组数据，给出一行输出，输出摆放的方案数目 CCC （数据保证 C<231C \lt 2^{31}C<231）。
输入输出样例
样例输入 #1
复制
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1样例输出 #1
复制
2 1#include<iostream> #include<vector> using namespace std; int n, k; const int N = 1e5; vector<bool>col(N, false); void dfs(int u, vector<vector<char>>g, 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; vector<vector<char>>g(n, vector<char>(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 , 表示这组测试数据的结束。如果一行上给出w=h=0w = h = 0w=h=0 ， 那么表示所有的输入结束 。
输出
对每一个矩形板， 输出一行 “ 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 i=1; i<=h; i++) { for(int j=1; j<=w; j++) { char ch = getchar(); while(ch != ' ' && ch != 'X') { ch = getchar(); } if(ch=='X') mp[i][j]=1; } }如果出现时间超限的问题请考虑切换搜索方向。
