建设银行网上银行网站进入不了,海南做网站的,网站功能策划,可遇公寓网站哪个公司做的题目
1756:八皇后 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 会下国际象棋的人都很清楚#xff1a;皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上#xff08;有8 * 8个方格#xff09;#xff0c;使它们谁也不能被吃掉皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上有8 * 8个方格使它们谁也不能被吃掉这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法定义一个皇后串a与之对应即ab1b2…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
理解
1.从第一列开始f(1)每列从第一行还是找皇后位置。 2for(int i1;i8;i) 3.找没用过的行、唯一斜行行列、唯一反斜行8行-列。 4.找到了该位置就是该行皇后位置。h[i]1,xk[xi]1,fx[8x-i]1。并存到字符串的该列位置 5.递归下一列f(l1)继续2-4 6.直到8行都有皇后了就算一个结果序列。 7.回溯撤销4行的设置改尝试2循环的下一行。
代码
#include bits/stdc.h using namespace std; bool k[9][9],//哪个坐标有皇后 h[18],//哪行已经有皇后了 xk[18],//哪个斜列有皇后了 fx[18];//哪个反斜列已经有皇后了 int n,//几组 b,//哪一组 m1;//第几组方案 string s[100]; void view(int x){ cout“No: “xendl; for(int i1;i8;i){ for(int j1;j8;j)coutk[i][j]” “;coutendl; } } void go(int l){//递归每行寻找一个可以放皇后得位置能放到第8列就可以否则回溯尝试下一行 if(l9){ //view(m); //coutm”\t”s[m]endl; s[m1]s[m]; //拷贝上次序列往下再修改 m; return;//该方案就结束 }//没有结束就继续找下一列 for(int i1;i8;i){//寻找该列可以放皇后的行 if(!h[i]!xk[li]!fx[8i-l]){//如果该行该斜列该反斜列没有皇后 k[l][i]1,h[i]1,xk[li]1,fx[8i-l]1;//确认该位置放值皇后 s[m][l-1]char(i‘0’);//该列位置是哪一行 go(l1);//该列放置后继续下一列 k[l][i]0,h[i]0,xk[li]0,fx[8i-l]0;//撤销该位置皇后放置回溯尝试下一行 } } } int main(){ //freopen(“data.cpp”,“r”,stdin); s[1] ;//字符串有8个位置 cinn; go(1);//从第一列开始 while(n–){ cinb;couts[b]endl; } return 0; }
小结
广搜用队列无差别寻找 深搜递归回溯有差别寻找 我认为都是事关图的概念。
