用1*2的骨牌去覆盖n*n的棋盘

admin

其中n为偶数，求有多少种覆盖的方法。

1. <p>#include <iostream>
   
2. #include <iomanip>
   
3. using namespace std;
   
4. const int n=4;   假设是4*4 的格子
   
5. int a[n*n];
   
6. int s=1;
   
7. void mysearch(int i)
   
8. {
   
9.     int j;
   
10.     if (i==n*n)
    
11.     {
    
12.         for (j=0; j<=n*n-1; j++)
    
13.         {
    
14.             cout<<setw(3)<<a[j];
    
15.             if (j%n==n-1) cout<<endl;
    
16.         }
    
17.         cout<<endl;
    
18.     }
    
19.     else if (a[i]>0)  mysearch(i+1);
    
20.     else
    
21.     {
    
22.         if (a[i+1]==0)
    
23.         {
    
24.             a[i]=a[i+1]=s++;
    
25.             mysearch(i+1);
    
26.             s--;
    
27.             a[i]=a[i+1]=0;
    
28.         }
    
29.         if (a[i+n]==0)
    
30.         {
    
31.             a[i]=a[i+n]=s++;
    
32.             mysearch(i+1);
    
33.             s--;
    
34.             a[i]=a[i+n]=0;
    
35.         }
    
36. }
    
37. }
    
38. int main()
    
39. {
    
40.     mysearch(0);
    
41.     return 0;
    
42. }
    

复制代码

admin

此题可以用一维数组或者二维数组做，区别不大，我的程序比较好记，可以参考。
也可以将记录骨牌序号的S作为参数带到mysearch函数里面去，见下

1. #include <iostream>
   
2. #include <iomanip>
   
3. using namespace std;
   
4. const int n=4;
   
5. int a[n*n];
   
6. int t=1;
   
7. void mysearch(int i,int s)
   
8. {
   
9.     if (i==n*n)
   
10.     {
    
11.         cout<<t++<<":"<<endl;
    
12.         for (int j=0; j<=n*n-1; j++)
    
13.         {
    
14.             cout<<setw(3)<<a[j];
    
15.             if (j%n==n-1) cout<<endl;
    
16.         }
    
17.         cout<<endl;
    
18.     }
    
19.     else if (a[i]>0)  mysearch(i+1,s);
    
20.     else
    
21.     {
    
22.         if ((i%n<=n-2) &&(a[i+1]==0))  //横着摆
    
23.         {
    
24.             a[i]=a[i+1]=s;
    
25.             mysearch(i+2,s+1); //a[i]和a[i+1]都放了骨牌，直接搜索i+2;
    
26.             a[i]=a[i+1]=0;
    
27.         }
    
28.         if ((i/n<=n-2)&&(a[i+n]==0))  //竖着摆
    
29.         {
    
30.             a[i]=a[i+n]=s;
    
31.             mysearch(i+1,s+1);
    
32.             a[i]=a[i+n]=0;
    
33.         }
    
34.     }
    
35. }
    
36. int main()
    
37. {
    
38.     mysearch(0,1);
    
39.     return 0;
    
40. }
    

复制代码

hr567

老师好像用递归做过，但是不及得了

/wjr/

1. #include<iostream>
   
2. #include<cstdlib>
   
3. using namespace std;
   
4. int a[1000][1000],n,tot,x0,y0;
   
5. void print()
   
6. {
   
7.         tot++;
   
8.         for(int x=1;x<=n;x++)
   
9.         {
   
10.                 for(int y=1;y<=n;y++)cout<<a[x][y]<<" ";
    
11.                 cout<<endl;
    
12.         }
    
13.         cout<<endl;
    
14. }
    
15. void mysearch(int i)
    
16. {
    
17.         int x,y;
    
18.         for(x=x0;x<=n;x++)
    
19.         for(y=y0;y<=n;y++)
    
20.         {
    
21.                 if(!a[x][y]&&!a[x+1][y])
    
22.                 {
    
23.                         a[x+1][y]=a[x][y]=i;
    
24.                         x0=x;y0=y;
    
25.                         mysearch(i+1);
    
26.                         a[x+1][y]=a[x][y]=0;
    
27.                         x0=0;y0=0;
    
28.                 }
    
29.                 if(!a[x][y]&&!a[x][y+1])
    
30.                 {
    
31.                         a[x][y]=a[x][y+1]=i;
    
32.                         x0=x;y0=y;
    
33.                         mysearch(i+1);
    
34.                         a[x][y]=a[x][y+1]=0;
    
35.                         x0=0;y0=0;
    
36.                 }
    
37.         }
    
38.         if(i==n*n/2)print();
    
39. }
    
40. int main()
    
41. {
    
42.         cin>>n;
    
43.         //if(n%2){cout<<"None!!";return 0;}
    
44.         for(int i=0;i<=n+1;i++)
    
45.                 a[0][i]=a[n+1][i]=a[i][n+1]=a[i][0]=-1;
    
46.         mysearch(1);
    
47.         cout<<tot;
    
48.         system("pause");return 0;
    
49. }

复制代码

这是我的，求改进。。

admin

还有一个做法，就是状压DP