fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. #define kom "Liczba bezpiecznych ustawień najwięk„szej liczby gońców na szachownicy n x n"
  6. #define Nmin 1		//minimalny rozmiar szachownicy
  7. #define Nmax 9		//maksymalny rozmiar szachownicy
  8. #define Nfig N*2-2	//liczba figur do ustawienia
  9. #define SKOCZEK 0	//0 - goniec, 1 - księżna(gońcoskoczek)
  10. #define POKAZ 0		//0 - tylko liczba, 1 - plansze, 2 - zajęte wiersze na przekątnych
  11.  
  12. int N,count;
  13.  
  14. bool D[Nmax*2]; 
  15.  
  16. struct plansza {bool P[Nmax][Nmax];
  17.   bool operator==(const plansza &P);
  18.   bool equals(plansza P);
  19.   void  symH();
  20.   bool eq_rot180(const plansza &P);
  21.   bool eq_rot90(const plansza &P);
  22.   bool eq_rot270(const plansza &P);
  23.   }P0,P;
  24. vector<plansza> tpl;
  25.  
  26. struct pozycje {int K[Nmax*2];}K;
  27.  
  28. //vector<pozycje> tp;
  29.  
  30. void show(const pozycje &P,int t);
  31. bool ss(int w, int k);
  32.  
  33. void uws(int p, int n) {
  34.   if (n==0) {
  35.     ++count;  
  36.     bool same=false;
  37.     for (int i=0;!same && i<tpl.size();++i)  same=tpl[i].equals(P);
  38.     if (!same) {
  39.       tpl.push_back(P);
  40.       show(K,POKAZ);
  41.       }
  42.     //tp.push_back(K); 
  43.     return;
  44.     }
  45.   if (p>2*N-1) return;
  46.   if (n<2*N-1-p) {
  47.     K.K[p]=-1;    
  48.     //printf("p[%d]=-1 -> p=%d,n=%d\n",p,p+1,n);
  49.     uws(p+1,n);
  50.     }    
  51.   int wp = p<N ? 0 : p-N+1;
  52.   int wk = p>=N ? N-1 : p;
  53.   for (int w = wp; w<=wk ;++w) {
  54.     int k=  p-w;
  55.     if (D[k-w+N]) continue;
  56.     if (SKOCZEK && !ss(w,p)) continue;
  57.     D[k-w+N]=true;
  58.     K.K[p]=w;
  59.     P.P[w][k]=true;
  60.     //printf("gs[%d,%d] -> p=%d,n=%d\n",w,k,p+1,n-1); show(K,1);
  61.     uws(p+1,n-1);
  62.     D[k-w+N]=false;
  63.     K.K[p]=-1;
  64.     P.P[w][k]=false;
  65.     }
  66.   }
  67.  
  68. int main() {
  69. puts(kom);
  70. printf("\tall\tdistinct\n");    
  71. for (N=Nmin;N<=Nmax;++N) {
  72.   //tp.clear();
  73.   tpl.clear();
  74.   count=0;
  75.   P=P0;
  76.   for(int i=0;i<2*N-1;++i) K.K[i]=-1;
  77.   uws(0,Nfig);
  78.   printf("n=%d\t%d\t%d\n",N,count,tpl.size());
  79. //  for(int i=0;i<tp.size();++i) {printf("%d\n",i);}
  80.   }
  81. return 0;
  82. }
  83.  
  84. //-------------------------------------------------------------
  85.  
  86. void show(const pozycje &P, int t) {
  87.   if (t==1) {
  88.     for (int i=0;i<N;++i) { 
  89.       for (int j=0;j<N;++j)
  90.         printf("%c",P.K[i+j]==i?'X':'o');
  91.       printf("\n");
  92.       }
  93.     printf("\n");
  94.     }
  95.   else if (t==2) {
  96.     for (int i=0;i<2*N-1;++i) 
  97.       printf("%d",P.K[i]);
  98.     printf("\n");
  99.     }
  100.   }
  101.  
  102. bool ss(int w, int p) {
  103.   if (p<2) return true;
  104.   if (K.K[p-1]>-1) {
  105.     if (w-K.K[p-1]==2) return false;
  106.     if (K.K[p-1]-w==1) return false;
  107.     }
  108.   if (p<3) return true;
  109.   if (K.K[p-3]>-1) {
  110.     if (w-K.K[p-3]==1) return false;
  111.     if (w-K.K[p-3]==2) return false;    
  112.     }
  113.   return true;
  114.   }
  115.  
  116. bool plansza::operator==(const plansza &Q) {
  117.   bool ok=true;    
  118.   for (int i=0;ok && i<N;++i)
  119.     for (int j=0;ok &&j<N;++j)
  120.       ok=P[i][j]==Q.P[i][j];
  121.   return ok;    
  122.   }
  123.  
  124. void plansza::symH() {
  125.   for (int i=0;i<N;++i)
  126.     for (int j=0;j<(N+1)/2;++j) {
  127.       bool p=P[i][j];
  128.       P[i][j]=P[i][N-1-j];
  129.       P[i][N-1-j]=p;
  130.       } 
  131.   };
  132.  
  133. bool plansza::eq_rot90(const plansza &Q) {
  134.   bool ok=true;
  135.   for (int i=0;ok&&i<N;++i)
  136.     for (int j=0;ok&&j<N;++j)
  137.        ok = Q.P[j][N-1-i]==P[i][j];
  138.   return ok;
  139.   }
  140.  
  141. bool plansza::eq_rot180(const plansza &Q) {
  142.   bool ok=true;
  143.   for (int i=0;ok&&i<N;++i)
  144.     for (int j=0;ok&&j<N;++j)
  145.        ok = Q.P[N-1-i][N-1-j]==P[i][j];
  146.   return ok;
  147.   }
  148.  
  149. bool plansza::eq_rot270(const plansza &Q) {
  150.   bool ok=true;
  151.   for (int i=0;ok&&i<N;++i)
  152.     for (int j=0;ok&&j<N;++j)
  153.        ok = Q.P[N-1-j][i]==P[i][j];
  154.   return ok;
  155.   }
  156.  
  157. bool plansza::equals(plansza P) {
  158.   if (eq_rot90(P)) return true;
  159.   if (eq_rot180(P)) return true;
  160.   if (eq_rot270(P)) return true;
  161.   P.symH();
  162.   if (*this==P) return true;
  163.   if (eq_rot90(P)) return true;
  164.   if (eq_rot180(P)) return true;
  165.   if (eq_rot270(P)) return true;
  166.   return false;
  167.   }
Success #stdin #stdout 0.45s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Liczba bezpiecznych ustawień najwięk„szej liczby gońców na szachownicy n x n
	all	distinct
n=1	1	1
n=2	4	1
n=3	8	2
n=4	16	3
n=5	32	6
n=6	64	10
n=7	128	20
n=8	256	36
n=9	512	72
https://ideone.com/DV8w8o
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!