搜索算法是 OI 中常用的一种算法, 除了 OI 以外, 在工程开发中, 搜索算法的应用也十分广泛, 如果你尝试自己写一些需要处理的数据量不是很大的工程, 你可能会发现你用到的算法只有搜索和模拟 搜索也是在考试中得分的一种重要手段, 我没统计过在一场考试中平均有多少分是搜索拿到的, 不过毫无疑问的是大家一定都通过搜索拿过不少分
1214: 八皇后
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 6039 通过数: 3687
[题目描述]
会下国际象棋的人都很清楚: 皇后可以在横, 竖, 斜线上不限步数地吃掉其他棋子. 如何将 8 个皇后放在棋盘上 (有 8 * 8 个方格), 使它们谁也不能被吃掉! 这就是著名的八皇后问题.
对于某个满足要求的 8 皇后的摆放方法, 定义一个皇后串 a 与之对应, 即 a=b1b2...b8a=b1b2...b8, 其中 bi 为相应摆法中第 i 行皇后所处的列数. 已经知道 8 皇后问题一共有 92 组解 (即 92 个不同的皇后串).
给出一个数 b, 要求输出第 b 个串. 串的比较是这样的: 皇后串 x 置于皇后串 y 之前, 当且仅当将 x 视为整数时比 y 小.
[输入]
第 1 行是测试数据的组数 n, 后面跟着 n 行输入. 每组测试数据占 1 行, 包括一个正整数 b(1≤b≤92).
[输出]
输出有 n 行, 每行输出对应一个输入. 输出应是一个正整数, 是对应于 b 的皇后串.
[输入样例]
2 1 92
[输出样例]
- 15863724
- 84136275
代码
- #include
- #include
- using namespace std;
- bool vis1[100]={0},vis2[100]={0},vis3[100]={0};
- int b[100]={0},map[100][100]={0},a[100];
- int k,n;
- void dfs(int x)
- {
- if(x==8+1)
- {
- k++;
- for(int i=1;i<=8;i++)
- map[k][i]=b[i];
- }
- for(int y=1;y<=8;y++)
- {
- if((!vis1[y])&&(!vis2[x+y])&&(!vis3[x-y+8]))
- {
- vis1[y]=1;
- vis2[x+y]=1;
- vis3[x-y+8]=1;
- b[x]=y;
- dfs(x+1);
- vis1[y]=0;
- vis2[x+y]=0;
- vis3[x-y+8]=0;
- }
- }
- }
- int main()
- {
- cin>>n;
- dfs(1);
- for(int i=1;i<=n;i++)
- cin>>a[i];
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=8;j++)
- cout<<map[a[i]][j];
- cout<<endl;
- }
- return 0;
- }
1215: 迷宫
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 17843 通过数: 5161
[题目描述]
一天 Extense 在森林里探险的时候不小心走入了一个迷宫, 迷宫可以看成是由 n * n 的格点组成, 每个格点只有 2 种状态,. 和 #, 前者表示可以通行后者表示不能通行. 同时当 Extense 处在某个格点时, 他只能移动到东南西北 (或者说上下左右) 四个方向之一的相邻格点上, Extense 想要从点 A 走到点 B, 问在不走出迷宫的情况下能不能办到. 如果起点或者终点有一个不能通行 (为 #), 则看成无法办到.
[输入]
第 1 行是测试数据的组数 k, 后面跟着 k 组输入. 每组测试数据的第 1 行是一个正整数 n (1 ≤ n ≤ 100), 表示迷宫的规模是 n * n 的. 接下来是一个 n * n 的矩阵, 矩阵中的元素为. 或者 #. 再接下来一行是 4 个整数 ha, la, hb, lb, 描述 A 处在第 ha 行, 第 la 列, B 处在第 hb 行, 第 lb 列. 注意到 ha, la, hb, lb 全部是从 0 开始计数的.
[输出]
k 行, 每行输出对应一个输入. 能办到则输出 "YES", 否则输出 "NO".
[输入样例]
- 2
- 3
- .##
- ..#
- #..
- 0 0 2 2
- 5
- .....
- ###.#
- ..#..
- ###..
- ...#.
- 0 0 4 0
[输出样例]
YES NO
代码
- #include
- #include
- using namespace std;
- int xr[4] = { 0,1,0,-1 };
- int yr[4] = { -1,0,1,0 };
- int x_1, x_2, y_1, y_2, T, n;
- char a;
- bool vsd[100][100], flag;
- void dfs(int x, int y) {
- if (flag) {
- return;
- }
- if ((x <0) || (y <0)) {
- return;
- }
- if ((x>= n) || (y>= n)) {
- return;
- }
- if (vsd[x][y]) {
- return;
- }
- vsd[x][y] = 1;
- if ((x == x_2) && (y == y_2)) {
- cout <<"YES" <<endl;
- flag = true;
- return;
- }
- for (int i = 0; i < 4; i++) {
- dfs(x + xr[i], y + yr[i]);
- }
- return;
- }
- int main() {
- cin>> T;
- for (int o = 1; o <= T; o++) {
- memset(vsd, false, sizeof(vsd));
- flag = false;
- cin>> n;
- for (int i = 0; i <n; i++) {
- for (int j = 0; j <n; j++) {
- cin>> a;
- if (a == '#') {
- vsd[i][j] = 1;
- }
- }
- }
- cin>> x_1>> y_1>> x_2>> y_2;
- if (vsd[x_1][y_1] || vsd[x_2][y_2]) {
- cout << "NO" << endl;
- continue;
- }
- else {
- dfs(x_1, y_1);
- }
- if (!flag) {
- cout << "NO" << endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3433690.html