• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            posts - 106,  comments - 32,  trackbacks - 0

            原始博客地址: http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/拿到題目我的第一反應是八皇后問題,順利的寫出了遞歸解法,弄完這個,感覺自己寫遞歸和回溯有了一定的進步了,至此第一章做完了,再接再厲。

            但是提交后,在13 這個測試樣例超時,然后就在想怎么剪枝

            • 之前在判斷放棋子是否沖突的時候,是在放的位置往四個方向拓展,如果沒有沖突就放 。現在改進為直接判斷 和之前放置的棋子是否沖突。
            • 對稱剪枝,這個在百度之后才知道的 ,這個是關鍵,直接砍掉一般的時間
            還有說是用位運算,這個不熟,下次去學一下。
            /*
            ID:fuxiang2
            PROG: checker
            LANG: C++
            */
            #include 
            <iostream>
            #include 
            <fstream>
            #include 
            <stack>
            #include 
            <string>
            #include 
            <vector>
            #include 
            <queue>
            #include 
            <map>
            #include 
            <list>
            #include 
            <algorithm>
            #include 
            <set>
            #include 
            <cmath>
            #include 
            <cstring>
            #include 
            <cstdlib>
             
            #define REP(i, n) for (int i=0;i<int(n);++i)
            #define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
            #define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
            #define REP_1(i, n) for (int i=1;i<=int(n);++i)
            #define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
            #define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
            #define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
             
            using namespace std;
            ofstream fout (
            "checker.out");
            ifstream fin (
            "checker.in");
             
            const int N = 14;
            int graph[N][N];
            int n;
            int ans ;
            int result ;
            // 類似八皇后問題
            int used[N];
            //list <int >path;
            int path[N];
             
            bool isok(int x,int y)
            {
                
            if(x >=1 && x<= n && y >= 1 && y <= n)
                    
            return true;
                
            return false;
            }
            int dir[4][2= { {-1,-1} ,{-1,1},{1,1},{1,-1} };
            bool check(int x,int y )
            {
                
            int nx = x;
                
            int ny = y;
                
            int n = x -1;
                
            if(n == 0)
                    
            return true;
             
                FOR_1(i,
            1,n){
                    nx 
            = i;
                    ny 
            = path[i];
                    
            if( abs(x-nx) == abs(y-ny))
                        
            return false;
                }
                
            return true;
             
                
            //FOR_1(i,0,3){
                
            //    nx = x +  dir[i][0];
                
            //    ny = y +  dir[i][1];
                
            //    while(isok(nx,ny) ){
                
            //        if(graph[nx][ny] == 1)
                
            //            return false;
                
            //        nx += dir[i][0];
                
            //        ny += dir[i][1];
                
            //    }
                
            //}
                
            //return true;
             
            }
             
            void place(int col,int row)
            {
                graph[row][col] 
            = 1;
                
            if(row== n){
                    ans 
            ++;
                    
            if(result + ans <= 3){
                        
            //list<int >::iterator iter = path.begin();
                        
            //fout<< *iter;
                        fout<<path[1];
                        
            //for(iter ++ ; iter != path.end() ; iter ++)
                        for(int i = 2 ; i <= n ; i ++)
                            fout 
            <<" "<< path[i];
                        fout
            <<endl;
                    }
                    graph[row][col] 
            = 0;
                    
            return ;
                }
                FOR_1(i,
            1,n){
                    
            if(used[i] == 0 && check(row+1,i ) == true )
                    {
                        path[row
            +1= i;//path.push_back(i);
                        used[i] = 1;
                        place(i,row
            +1);
                        
            //path.pop_back();
                        used[i] = 0;
                    }
                }
                graph[row][col] 
            = 0;
             
            }
            void work(int n)
            {
                result 
            = 0;
             
                FOR_1(j,
            1,n/2) {// 列
                    path[1= j;//path.push_back(j);
                    used[j]  = 1;
                    place(j,
            1);
                    
            //path.pop_back();
                    used[j] = 0;
                }
                
            int re =  ans;
                result 
            = ans;
                
            if(re <3 || n%2 == 1){
                    
            int t = n/2 + 1;
                    ans 
            = 0;
                    path[
            1= t;//path.push_back(j);
                    used[t]  = 1;
                    place(t,
            1);
             
                }
                
            if( n% 2 == 1)
                    result 
            += re + ans;
                
            else
                    result 
            += re;
            }
             
            int main()
            {
                fin
            >>n;
                work(n);
                fout
            << result<<endl;
                
            return 0;
             
            }

            原始博客地址: http://www.fuxiang90.com/2012/07/usaco1-5-checker-challenge/
            posted on 2012-07-10 10:41 付翔 閱讀(220) 評論(0)  編輯 收藏 引用

            <2011年2月>
            303112345
            6789101112
            13141516171819
            20212223242526
            272812345
            6789101112

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品欧美日韩精品| 国产精品成人99久久久久| 三级三级久久三级久久| 亚洲色欲久久久综合网东京热| 伊人久久大香线蕉综合影院首页 | 色综合久久最新中文字幕| 亚洲国产精品久久| 97精品依人久久久大香线蕉97| 99久久精品国内| 久久免费视频1| 日本精品久久久久中文字幕| 怡红院日本一道日本久久| 久久综合久久鬼色| 精品免费久久久久久久| 人妻少妇精品久久| 久久国产精品久久国产精品| 久久婷婷色综合一区二区| 成人久久精品一区二区三区| 久久精品无码免费不卡| 国产精品一久久香蕉产线看| 日本久久中文字幕| 久久99精品久久久久久9蜜桃| 久久超乳爆乳中文字幕| 久久这里只有精品首页| 久久久人妻精品无码一区| 99久久婷婷免费国产综合精品| 久久精品中文无码资源站| 久久99国产精品成人欧美| 久久精品国产免费一区| 国产精品久久久久aaaa| AV无码久久久久不卡网站下载 | 无码人妻久久一区二区三区免费丨| 国产精品99久久久久久www| 久久九九全国免费| 国产成人久久AV免费| 国产精品18久久久久久vr| 一本大道久久a久久精品综合| 精品精品国产自在久久高清| 久久精品国产影库免费看| 国产成人精品久久| 久久亚洲高清综合|