Hi, I have accepted in 14 seconds, but limit is 15s
![:D](./images/smilies/icon_biggrin.gif)
How to improve speed ? It's strange problem. I have almost all in arrays and still high time...
Moderator: Board moderators
Code: Select all
#pragma warning(disable:4786)
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
int col,CNT;
int dia1,dia2;
int n;
int row[20];
int cnt[20];
int XX;
int p2[30];
void PLACE(int at)
{
int i,ok,j,temp,x;
int prev,now;
int ff,kk;
if(at==n)
{
CNT++;
return;
}
for(i=0;i<n;i++)
if(!(col&(p2[i])) && !(row[at]&(p2[i])) && !(dia1&(p2[at+i])) && !(dia2&(p2[at-i+n-1])) )
{
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
ok=1;
for(j=at+1;j<n && ok;j++)
{
ff=((dia2>>(j))&(XX));
kk=0;
for(x=0;x<n;x++)
{
kk=(kk<<1) | (ff&1);
ff>>=1;
}
temp=col | row[j] | ((dia1>>(j))&(XX)) | kk;
if(temp==XX)
ok=0;
}
if(ok)
PLACE(at+1);
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
}
}
int main()
{
int ks=0;
int i,j;
char B[20][20];
int ok;
int x;
int p;
int ans[]={0,0, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184 };
p2[0]=1;
for(i=1;i<30;i++)
p2[i]=p2[i-1]<<1;
while(scanf("%d",&n)!=EOF && n)
{
XX=p2[n]-1;
dia1=dia2=0;
printf("Case %d: ",++ks);
for(i=0;i<n;i++)
scanf("%s",B[i]);
ok=1;
p=0;
for(i=0;i<n;i++)
{
cnt[i]=row[i]=0;
for(j=0;j<n;j++)
{
cnt[i]+=(x=(B[i][j]=='*'));
if(x)
row[i]|=p2[j];
p|=x;
}
if(cnt[i]==n) ok=0;
}
if(p==0)
{
printf("%d\n",ans[n]);
continue;
}
if(!ok)
{
printf("0\n");
continue;
}
CNT=col=0;
PLACE(0);
printf("%d\n",CNT);
}
return 0;
}
Code: Select all
void PLACE(int at)
{
if(at==n) {
CNT++;
return;
}
for(int i=0;i<n;i++)
if(!(col&(p2[i])) && !(row[at]&(p2[i])) && !(dia1&(p2[at+i])) && !(dia2&(p2[at-i+n-1])) ) {
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
PLACE(at+1);
col=col^p2[i];
dia1^=p2[at+i];
dia2^=p2[at-i+n-1];
}
}
Code: Select all
...
if(!(col & b) && !(row[at] & b) && !(dia1 & (1 << (at+i))) && !(dia2 & (1 << (at-i+n-1))) ) {
...
Code: Select all
void PLACE(int at, int col, int dia1, int dia2)
{
if(at==n) {
CNT++;
return;
}
for(int i = 0, b = 1; i < n; i++, b <<= 1)
if(!(tmp & b) && !(row[at] & b) && !(dia1 & (1 << (at+i))) && !(dia2 & (1 << (at-i+n-1))))
PLACE(at+1, col ^ b, dia1 ^ (1 << (at+i)), dia2 ^ (1 << (at-i+n-1)));
}
Code: Select all
void PLACE(int at, int col, int dia1, int dia2)
{
if(at==n) {
CNT++;
return;
}
int tmp = ( ??? operation with col, row[at], dia1, dia2 ...);
for(int i = 0, b = 1; i < n; i++, b <<= 1)
if(!(tmp & b))
PLACE(at+1, .....);
}
Code: Select all
-tmp & tmp
If there are many bad squares, the ordinary counting way (counting the solutions without using bad squares) is fast, but if there are only few bad squares, counting solutions with using at least one bad squares is faster.(without using bad squares) = (maximum) - (with using at least one bad square)
Write a little program that prints the bits and look how -tmp & tmp works. I think you could understand it.sonyckson wrote:Hello!!!.. i did my program with backtracking, complementary sets, and a little more ideas...it was not very efficient (not at all )...so I got 10...seconds... I have been reading your posts, but i cant understand what is that of -tmp&tmp....
Sory but I don't know any links.sonyckson wrote:I also wonder if you could give me any link to any good place to read about this kind of optimizations ( in c, c++ )