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


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


		
          
		
          一開始什么優(yōu)化都沒有，過不了了（記得以前是可以的啊）
          然后用了三個(gè)hash數(shù)組記錄各列、對角線棋子的放置情況，再加上左右對稱解的優(yōu)化，總算在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;
          }
          

          

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




主站蜘蛛池模板：
收藏|
砀山县|
突泉县|
旬邑县|
多伦县|
昆明市|
延吉市|
上蔡县|
丹东市|
黄山市|
三穗县|
高尔夫|
盘山县|
孝感市|
闽清县|
穆棱市|
满城县|
白河县|
称多县|
得荣县|
胶南市|
宿迁市|
融水|
樟树市|
伊春市|
那曲县|
惠州市|
正镶白旗|
郧西县|
金秀|
南乐县|
临洮县|
松江区|
许昌县|
叶城县|
外汇|
禄劝|
奉化市|
宜兴市|
大安市|
长顺县|