学步园

比起普通的搜索剪枝来，由于在每一层的搜索里多加了两个限定条件ld/rd——斜对角线，加之使用取最低位的操作，大大减少了每一层的遍历时间。

这是USACO1.5的最后一题，要求列出字典序遍历结果的前三位。在N=13的情形下，运行时间0.163S。

/*<br /> ID: C.D.<br /> PROG: checker<br /> LANG: C++<br /> */</p> <p>#include <iostream><br /> #include <fstream><br /> #include <string><br /> #include <algorithm><br /> using namespace std;</p> <p>int Ans;<br /> int N;<br /> int Mask;<br /> int Case;<br /> int Path[20];</p> <p>ifstream fin ( "checker.in" );<br /> ofstream fout ( "checker.out" );</p> <p>int log2 ( int n )<br /> {<br /> if ( n == 1 )<br /> return 0;<br /> return log2 ( n >> 1 ) + 1;<br /> }</p> <p>void print ()<br /> {<br /> int i;<br /> for ( i = 0; i < N; i ++ )<br /> {<br /> if ( i )<br /> fout << " ";<br /> fout << Path[i];<br /> }<br /> fout << endl;<br /> }</p> <p>void dfs ( int x, int ld, int rd )<br /> {<br /> if ( x == Mask )<br /> {<br /> Ans ++;<br /> return;<br /> }<br /> int avail = ~ ( x | ld | rd ) & Mask;<br /> int i;<br /> while ( avail )<br /> {<br /> i = avail & ( -avail ); // 取最低位<br /> avail -= i;<br /> dfs ( x + i, ( ld + i ) << 1, ( rd + i ) >> 1 );<br /> }<br /> }</p> <p>void dfs3 ( int depth, int x, int ld, int rd )<br /> {<br /> if ( Case >= 3 )<br /> return;<br /> if ( x == Mask )<br /> {<br /> Case ++;<br /> print ();<br /> return;<br /> }<br /> int avail = ~ ( x | ld | rd ) & Mask;<br /> int i;<br /> while ( avail )<br /> {<br /> i = avail & ( -avail );<br /> Path[depth] = log2 ( i ) + 1;<br /> avail -= i;<br /> dfs3 ( depth + 1, x + i, ( ld + i ) << 1, ( rd + i ) >> 1 );<br /> }<br /> }</p> <p>int main ()<br /> {<br /> fin >> N;<br /> Mask = ( 1 << N ) - 1;<br /> Ans = 0, Case = 0;<br /> dfs3 ( 0, 0, 0, 0 );<br /> dfs ( 0, 0, 0 );<br /> fout << Ans << endl;<br /> return 0;<br /> }