华师一附中OI组

标题: 用1*2的骨牌去覆盖n*n的棋盘 [打印本页]
作者: admin    时间: 2014-10-23 10:47
标题: 用1*2的骨牌去覆盖n*n的棋盘
其中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. }
复制代码


作者: hr567    时间: 2014-10-23 21:08
老师好像用递归做过，但是不及得了
作者: admin    时间: 2014-10-25 17:41
此题可以用一维数组或者二维数组做，区别不大，我的程序比较好记，可以参考。
也可以将记录骨牌序号的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. }
复制代码

作者: /wjr/    时间: 2014-10-28 18:43
  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    时间: 2018-8-24 11:22
还有一个做法，就是状压DP



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2