<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        





    
	
    
		
			


    
	
    

    posts - 403, comments - 310, trackbacks - 0, articles - 7
    
	
 
BlogJava ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理


    
		    		
	
    
	
    
		
			
    
			
    
		    		
		
			
    
				
					
	
    
		
    
			
    
				USACO 1.1.5 Checker Challenge
			
    
 			Posted on 2007-06-03 19:22 ZelluX 閱讀(604) 評論(0)  編輯  收藏  所屬分類: Algorithm 
			
			


		
    
		
    一開始什么優化都沒有，過不了了（記得以前是可以的啊）
    然后用了三個hash數組記錄各列、對角線棋子的放置情況，再加上左右對稱解的優化，總算在0.828秒里過了

    /*
    PROG: checker
    ID: 06301031
    LANG: C++
    */

    #include     <iostream>
    #include     <fstream>

    using namespace std;

    int g[13];
    bool column[13], diag1[25], diag2[25];
    int n;
    int countResult = 0;
    int mid = 0, firstHalf = 0;
    ifstream fin(    "checker.in");
    ofstream fout(    "checker.out");

    void DFS(int t) {
            int i;
            if (t == n) {
            countResult    ++;
                if (countResult <= 3) {
                fout     << g[0] + 1;
                    for (i = 1; i < n; i++) {
                    fout     << " " << g[i] + 1;
                }
                fout     << endl;
            }
                return;
        }

            for (g[t] = 0; g[t] < n; g[t]++) {
                if ((countResult > 3) && (t == 0)) {
                    if (g[t] == n / 2) {
                    firstHalf     = countResult;
                        if (n % 2 == 0) {
                        fout     << firstHalf * 2 << endl;
                        exit(    0);
                    }
                }
                    if ((g[t] == n / 2 + 1) && (n % 2 == 1)) {
                    mid     = countResult - firstHalf;
                    fout     << firstHalf * 2 + mid << endl;
                    exit(    0);
                }
            }
                if (column[g[t]]) {
                    continue;
            }
                if (diag1[g[t] + t]) {
                    continue;
            }
                if (diag2[g[t] - t + n]) {
                    continue;
            }

            diag1[g[t]     + t] = true;
            diag2[g[t]     - t + n] = true;
            column[g[t]]     = true;
            DFS(t     + 1);
            diag1[g[t]     + t] = false;
            diag2[g[t]     - t + n] = false;
            column[g[t]]     = false;

    nextPosition:
            ;
        }
    }

    int main() {
        fin     >> n;
            int i;
            for (i = 0; i < n; i++) {
            column[i]     = false;
        }
            for (i = 0; i < n * 2 -1; i++) {
            diag1[i]     = false;
            diag2[i]     = false;
        }
        DFS(    0);
        fout     << countResult << endl;
        fout.close();
            return 0;
    }
    

    

    
	
    
	


    
	    
    




    








    

				
			
    
		    		
	
    
	
    
		
			


		
	
    

    



    







    
        
	



主站蜘蛛池模板：
日本一线a视频免费观看|
久久一本岛在免费线观看2020|
真人做人试看60分钟免费视频
|
caoporn成人免费公开|
国产精品国产午夜免费福利看|
亚洲综合偷自成人网第页色|
成人免费一级毛片在线播放视频|
亚洲日韩乱码中文无码蜜桃
|
久久久久亚洲?V成人无码|
视频免费1区二区三区|
免费人成年激情视频在线观看|
国产亚洲午夜精品|
免费一级成人毛片|
aaa毛片视频免费观看|
亚洲免费人成在线视频观看|
国产一精品一AV一免费|
亚洲Av熟妇高潮30p|
亚洲成年人免费网站|
亚洲精品二三区伊人久久|
成人毛片18女人毛片免费96|
亚洲av永久无码|
91麻豆精品国产自产在线观看亚洲
|
一级一黄在线观看视频免费|
亚洲一区二区三区偷拍女厕
|
日韩一级免费视频|
麻豆91免费视频|
精品亚洲永久免费精品|
1000部夫妻午夜免费|
亚洲愉拍一区二区三区|
国产yw855.c免费视频|
日韩精品无码免费专区午夜|
亚洲欧洲久久精品|
四虎影视永久免费观看网址|
国产特黄特色的大片观看免费视频|
亚洲国产精品一区二区第一页|
91手机看片国产永久免费|
狼人大香伊蕉国产WWW亚洲|
国产精品亚洲а∨无码播放|
成人免费一级毛片在线播放视频|
黄色网址大全免费|
亚洲精品无码久久毛片波多野吉衣|