lib/Documentation/docs-sonyckson/ajedrez.cpp

   1 // PORFAVOR NUNCA BORRAR ESTE PROBLEMA::: COSTO UN OJO DE LA CARA....
   2
   3 #include <algorithm>
   4 #include <vector>
   5 #include <set>
   6 #include <string>
   7 #include <fstream>
   8 #include <iostream>
   9 #include <iomanip>
  10 #include <map>
  11 #include <stack>
  12 #include <sstream>
  13 #include <queue>
  14
  15 #include <cmath>
  16 #include <cstdio>
  17 #include <cctype>
  18 #include <cstdlib>
  19 #include <cstring>
  20
  21 #define forn(i, n) for(int i=0;i<int(n);i++)
  22 #define foreach(it, c)  for(typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  23 #define ALL(x)   (x).begin(),(x).end()
  24 #define SORT(x) sort(ALL(x))
  25 using namespace std;
  26 #define VI vector<int>
  27 #define VS vector<string>
  28 int table[15];
  29 int N,cant;
  30 short pre[365597][14];
  31 int res = 0;
  32 #include <time.h>
  33 char arr[16][16];
  34 int ar[14];
  35 int tr(int ind){
  36         forn(i, 14){
  37                 int k = pre[ind][i];
  38                 if(arr[i][k]=='*')return 0;
  39         }
  40         return 1;
  41 }
  42 void bick(int paso, int columna, int subida, int bajadas){
  43         if(paso==14) {
  44                 forn(i, 14) pre[cant][i] = ar[i];
  45                 cant++;
  46                 return;
  47         }
  48         for(int i = 0, b = 1; i < N; i++, b <<= 1){
  49                 if(!(columna&b) && !(subida&(1<<(paso+i))) && !(bajadas&(1<<(paso-i+N-1)))&&!(table[paso]&b)){
  50                         ar[paso] = i;
  51                         bick(paso+1, columna^b, subida^(1<<(paso+i)),bajadas^(1<<(paso-i+N-1)));
  52                 }
  53         }
  54 }
  55 int M[1<<15];
  56 void back(int paso, int columna, int subida, int bajadas){
  57         if(paso==N-1) {
  58                 printf("hola\n");
  59                 for(int i = 0, b = 1; i < N; i++, b <<= 1){
  60                         if(!(columna&b) && !(subida&(1<<(paso+i))) && !(bajadas&(1<<(paso-i+N-1)))&&!(table[paso]&b))
  61                                 res++;
  62                 }
  63                 return;
  64         }
  65         if(paso==0){
  66                 for(int i = 0, b = 1; i < N; i++, b <<= 1)
  67                         if(!(table[paso]&b))
  68                                 back(paso+1, columna^b, subida^(1<<(paso+i)),bajadas^(1<<(paso-i+N-1)));
  69                 return;
  70         }
  71         int tmp = columna & (subida/(1<<paso)) & (bajadas/(1<<//& table[paso];
  72         int b;
  73         while(b=(-tmp&tmp)){
  74                 back(paso+1, columna^b, subida^(1<<(paso+M[b])),bajadas^(1<<(paso-M[b]+N-1)));
  75                 printf("hoa\n");
  76         }
  77 }
  78 int main(){
  79         for(int i=0;i<15;i++) M[1<<i] = i;
  80         cant=0;
  81         N=14;
  82         int i,j ,k, b;
  83         int casos = 0;
  84         int ans[]={0,0, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184 };
  85 //      bick(0,0,0,0);
  86         //printf("%i cant\n", cant);
  87         while(1){
  88                 scanf("%i", &N);
  89                 if(N==0)return 0;
  90                 casos++;
  91                 for(i=0;i<N;i++)table[i]=0;
  92                 k=0;
  93                 for(i=0;i<N;i++){
  94                         scanf("%s", arr[i]);
  95                         for(j=0, b = 1;j<N;j++, b<<=1){
  96                                 if(arr[i][j]=='*'){table[i]^=b;k++;}
  97                         }
  98                 }
  99                 /*
 100                 if(N==14){
 101                         res=0;
 102                         forn(i, 365596){
 103                                 if(tr(i))res++;
 104                         }
 105                 }
 106                 else{*/
 107                 res = 0;
 108                 //if(k>0)
 109                 back(0,0,0,0);
 110                 //      else res = ans[N];
 111                 //}
 112                 printf("Case %i: %i\n",casos, res);
 113         }
 114         return 0;
 115 }