1.adgԴ?单词量测试源码?
adgԴ??
代码如下：#include <iostream>#include <cstdio>
#define UINT unsigned int
#define ULL unsigned long long
#define MAXN ;
using namespace std;
int N,ans,minstep;
UINT Row,Col;
UINT Lft,Rgt;
inline UINT lowbit(UINT x){
return x&(-x);
}
bool check(){
UINT tR=~Row,tC;
UINT curR,curC;
while(tR){
curR=lowbit(tR);
tR ^= curR;
tC = ~Col;
while(tC){
curC=lowbit(tC);
tC^=curC;
if((Rgt & (curR*curC))!=0 || (Lft & ((1<<(N-1))/curR*curC))!=0)
continue;
return false;
}
}
return true;
}
void dfs(int row,int used,UINT col,UINT dig,UINT adg){
if(used>minstep)
return;
if(row == N){
if(check()){
if(used < minstep){
minstep = used;
ans=0;
}
ans++;
}
return;
}
UINT status=~(col|dig|adg);
UINT binRow=(1<<row);
while(status){
UINT t=status&(-status);
Col^=t;
Row^=binRow;
Lft^=((1<<(N-1))/binRow*t);
Rgt^=(binRow*t);
dfs(row+1,used+1,(t|col),(t|dig)>>1,(t|adg)<<1);
Col^=t;
Row^=binRow;
Lft^=((1<<(N-1))/binRow*t);
Rgt^=(binRow*t);
status^=t;
}
dfs(row+1,used,col,dig>>1,adg<<1);
}
int main(){
while(cin>>N){
UINT col=(1<<N)-1;
col=~col;
ans=0;
minstep=N+1;
Row=Col=col;
Rgt=Lft=0;
dfs(0,0,col,0,0);
cout<<minstep<<endl<<ans<<endl;
}
return 0;
}