华师一附中OI组

标题: 1209讲义 [打印本页]

---

作者: diggersun    时间: 2015-12-13 11:44
标题: 1209讲义

8皇后问题

有一个难点是判断在同一列，同一对角线的情况，考虑他的斜率就很好理解了

1. #include <iostream>
   
2. using namespace std;
   
3. int a[8];
   
4. bool b1[8],b2[16],b3[16]; //分别表示列，左对角线，右对角线是否可以放
   
5. 
   
6. void mysearch1(int i)
   
7. {
   
8.     int j,k;
   
9.     if (i>=8)  {for (j=0; j<=7; j++) cout <<a[j]<<' '; cout<<endl; }
   
10.     else  for (k=0; k<=7; k++)
    
11.         { if (b1[k] && b2[i+k] && b3[i-k+8])
    
12.             {   a[i]=k;
    
13.                 b1[k]=b2[i+k]=b3[i-k+8]=false; //体会这里的置位情况  斜率关系
    
14.                 mysearch1(i+1);
    
15.                 b1[k]=b2[i+k]=b3[i-k+8]=true;
    
16.             }
    
17.         }
    
18. }
    
19. bool canplace (int i ,int j)
    
20. {
    
21.     bool b=true;
    
22.     for (int k=0; k<=i-1; k++)
    
23.         if ((a[k]==j) ||(a[k]-k==i-j)||(a[k]+k==i+j)) b=false;
    
24.     return b;
    
25. }
    
26. void mysearch2(int i)
    
27. {
    
28.     int j,k;
    
29.     if (i>=8){for (j=0; j<=7; j++) cout <<a[j]<<' ';   cout<<endl;   }
    
30.     else  for (k=0; k<=7; k++)
    
31.             if (canplace(i,k))    {a[i]=k; mysearch2(i+1); }
    
32. }
    
33.     int main()
    
34.     {   for (i=0; i<=7; i++) b1[i]=true;
    
35.         for (i=0; i<=15; i++) b2[i]=b3[i]=true;
    
36.         mysearch2(0);
    
37. }
    
38. 
    
39. 
    
40. 间隔排列
    
41. #include<iostream>
    
42. using namespace std;
    
43. int n=3;
    
44. int i,a[100],b[100];
    
45. void mysearch(int i)
    
46. {  int j,k;
    
47.    if (i>=2*n) {for(j=0;j<=2*n-1;j++) cout<<a[j]+1;cout<<endl;} //递归出口，当2*N的位子上都摆满了
    
48.    else  if (a[i]>-1) mysearch(i+1);  //若此位置已经有数字了，就直接搜索下一个
    
49.    else
    
50.      for (k=0;k<=n-1;k++)
    
51.         if ((a[i]==-1) && (i+k+2<=2*n-1) && (a[i+k+2]==-1) && b[k])
    
52.             //四个条件 1此位置没有数字，2此数字没有被占用 3间隔一定位置后面的那个数字不超范围4也没有数字
    
53.    {    a[i]=a[i+k+2]=k;b[k]=false;mysearch(i+1);
    
54.         a[i]=a[i+k+2]=-1;b[k]=true;
    
55.    }
    
56. }
    
57. int main()
    
58. {
    
59.     for (i=0;i<=2*n-1;i++) a[i]=-1;
    
60.     for (i=0;i<=n-1;i++) b[i]=true;
    
61.     mysearch(0);
    
62.     }
    
63. 
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2