Question

浙大acm中1002题目请教

C语言版的，谢谢

Answer 1

# include <iostream>
# define _clr(aa) (memset(aa,0,sizeof(aa)))
using namespace std;
int n,a[20],ans;
bool check(int ch,int &b)
{
int i,j,c,z;
for(i=1,b=0;i<=n;i++)
{
for(j=(i-1)*n+1,c=z=0;j<=i*n;j++)
{
if( ch & (1<<j) ) c++;
if(a[j]) z++;
if(c>=2 && !z) return 0;
}
if(c>2) return 0;
for(j=i,c=z=0;j<=n*n;j+=n)
{
if( ch & (1<<j) ) c++;
if(a[j]) z++;
if(c>=2 && !z) return 0;
}
if(c>2) return 0;
}
for(i=1;i<=n*n;i++) if(ch & (1<<i)) b++;
return 1;
}int main()
{
int i,can,to,tm;
char t;
while(cin>>n,n)
{
_clr(a);
can = 0;
for(i=1;i<=n*n;i++)
{
cin>>t;
if(t=='X')
{
can |= (1<<i);
a[i]=1;
}
}
for(i=ans=0,to=1<<(n*n+1);i<=to;i+=2)
{
if(!(can & i) && check(i,tm) && ans<tm) ans=tm;
}
cout<<ans<<endl;
}
return 0;
}才采用穷举 二进制表示比一般的dfs要容易理解