| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
第一个搜索题就过,发个贴,庆祝一下......#include<stdio.h>
#include<math.h>
int chess[4][4];
int best;
int count;
void inicial()
{
best=0;
count=0;
}
int isok(int x,int n,int y)
{
int i,j;
for(i=0;i<n;i++)
{
if(chess[x][i]==-1)
{
if(abs(y-i)==1){return 0;}
else if(abs(y-i)==2)
{
if(chess[x][(y+i)/2]==0){return 0;}
}
else if(abs(y-i)==3)
{
if(chess[x][1]==0&&chess[x][2]==0)
{
return 0;
}
}
}
}
for(i=0;i<n;i++)
{
if(chess[i][y]==-1)
{
if(abs(x-i)==1){return 0;}
else if(abs(x-i)==2)
{
if(chess[(x+i)/2][y]==0){return 0;}
}
else if(abs(x-i)==3)
{
if(chess[1][y]==0&&chess[2][y]==0){return 0;}
}
}
}
return 1;
}
void recover(int n)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(chess[i][j]==-1){chess[i][j]=0;}
}
}
void search(int x,int n)
{
int i,j;
if(x>=n)
{
if(count>best)
{
best=count;
}
}
else
{
for(i=0;i<n;i++)
{
if(isok(x,n,i)&&chess[x][i]==0)
{
count++;
chess[x][i]=-1;
search(x,n);
count--;
chess[x][i]=0;
}
}
search(x+1,n);
}
}
main()
{
int n,i,j;
char c[5],f;
while(scanf("%d",&n)==1)
{
if(n==0)break;
inicial();
getchar();
for(i=0;i<n;i++)
{
gets(c);
for(j=0;j<n;j++)
{
f=c[j];
if(f=='.')
{
chess[i][j]=0;
}
else if(f=='X')
{
chess[i][j]=1;
}
}
}
search(0,n);
printf("%d\n",best);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator