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


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
          
			
          
				USACO 1.1.5 Checker Challenge
			
          
 			Posted on 2007-06-03 19:22 ZelluX 閱讀(602) 評(píng)論(0)  編輯  收藏  所屬分類(lèi): Algorithm 
			
			


		
          
		
          一開(kāi)始什么優(yōu)化都沒(méi)有，過(guò)不了了（記得以前是可以的啊）
          然后用了三個(gè)hash數(shù)組記錄各列、對(duì)角線棋子的放置情況，再加上左右對(duì)稱(chēng)解的優(yōu)化，總算在0.828秒里過(guò)了

          /*
          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;
          }
          

          

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




主站蜘蛛池模板：
洛隆县|
富锦市|
潮安县|
察雅县|
阜阳市|
庆阳市|
万荣县|
合江县|
西盟|
昭苏县|
青河县|
寻甸|
府谷县|
常德市|
竹溪县|
屏山县|
松溪县|
阿城市|
乌恰县|
彭州市|
桦甸市|
荔波县|
岢岚县|
台湾省|
崇州市|
武安市|
新营市|
潜山县|
灵山县|
天柱县|
富锦市|
宝应县|
九龙坡区|
错那县|
舟曲县|
军事|
沧源|
莎车县|
临漳县|
永济市|
米脂县|