• <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>

            學(xué)習(xí)心得(code)

            superlong@CoreCoder

              C++博客 :: 首頁(yè) :: 聯(lián)系 :: 聚合  :: 管理
              74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

            公告

            文字可能放在http://blog.csdn.net/superlong100,此處存放代碼

            常用鏈接

            留言簿(4)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            最新隨筆

            最新評(píng)論

            • 1.?re: Poj 1279
            • 對(duì)于一個(gè)凹多邊形用叉積計(jì)算面積 后能根據(jù)結(jié)果的正負(fù)來(lái)判斷給的點(diǎn)集的時(shí)針?lè)较颍?
            • --bsshanghai
            • 2.?re: Poj 3691
            • 你寫(xiě)的這個(gè)get_fail() 好像并是真正的get_fail,也是說(shuō)fail指向的串并不是當(dāng)前結(jié)點(diǎn)的子串。為什么要這樣弄呢?
            • --acmer1183
            • 3.?re: HDU2295[未登錄](méi)
            • 這個(gè)是IDA* 也就是迭代加深@ylfdrib
            • --superlong
            • 4.?re: HDU2295
            • 評(píng)論內(nèi)容較長(zhǎng),點(diǎn)擊標(biāo)題查看
            • --ylfdrib
            • 5.?re: HOJ 11482
            • 呵呵..把代碼發(fā)在這里很不錯(cuò)..以后我也試試...百度的編輯器太爛了....
            • --csuft1

            閱讀排行榜

            評(píng)論排行榜

            #include <iostream>
            #include 
            <string.h>
            #include 
            <queue>

            using namespace std;

            bool h[2][370000];
            int step;

            typedef 
            struct nod
            {
                
            char s[10];
                nod(){}
                
            void write(){
                    puts(s);
                }
            }cstring;


            queue
            < cstring > q[2];

            int sta[3][3], end[3][3];

            inline 
            void read(int st[][3])  //讀入函數(shù) 
            {
                
            for(int i = 0; i < 3; i ++)
                
            for(int j = 0; j < 3; j ++)
                    scanf(
            "%d"&st[i][j]);
            }

            inline 
            int nx(cstring str)      //求逆序數(shù) 
            {
                
            int l = strlen(str.s), i, j, num;
                num 
            = 0;
                
            for(i = 0; i < l; i ++)
                {
                    
            if(str.s[i] == '0'continue;
                    
            for(j = 0; j < i; j ++)
                    
            if(str.s[j] > str.s[i]) num ++;
                }
                
            //printf("%d\n",num);
                return num;
            }

            inline 
            int map(cstring str)        //映射 
            {
                
            int i, j, base, cnt, hash;
                
            base  = 1; hash = 0;
                
            for(i = 0; i < 9; i ++)
                {
                    
            if(str.s[i] == '0') str.s[i] = '9';
                    
            if(base == 0base = 1;
                    
            base *= i; cnt = 0;
                    
            for(j = 0; j < i; j ++)
                    
            if(str.s[j] > str.s[i]) cnt ++;
                    hash 
            += base * cnt;
                }
                
            return hash;
            }

            inline 
            void swap(char &a, char &b)   //交換函數(shù) 
            {
                
            char c = a; a = b; b = c;
            }

            void change(cstring &tp, int dic) //4種擴(kuò)展 
            {
                
            int i, j, l = strlen(tp.s);
                
            char tmp;
                
            //up right down left

                
            for(i = 0; i < l; i ++)
                
            if(tp.s[i] == '0'break;
                
            if(dic == 0 && i > 2
                    swap(tp.s[i], tp.s[i 
            - 3]);
                
            else if(dic == 1 && i % 3 != 2
                    swap(tp.s[i], tp.s[i 
            + 1]);
                
            else if(dic == 2 && i < 6)
                    swap(tp.s[i], tp.s[i 
            + 3]);
                
            else if(dic == 3 && i % 3 != 0)
                    swap(tp.s[i], tp.s[i 
            - 1]);
                
            else strcpy(tp.s, " ");

            }

            int extend(int index, cstring st) //擴(kuò)展函數(shù) 
            {
                cstring tp;
                
            int i, j, l = strlen(st.s), hash;  
                
            for(i = 0; i < 4; i ++)
                {
                    strcpy(tp.s ,st.s);
                    change(tp, i);
                    
            if(strcmp(tp.s," "))
                    {
                        
            //tp.write();
                        hash = map(tp);
                        
            if(h[index][hash]) continue;
                        
            if(h[1 - index][hash]) return true;
                        q[index].push(tp);
                        h[index][hash] 
            = 1;
                    }
                }
                
            return false;



            void atos(int arr[3][3], cstring &tp_atos) //把數(shù)組變成cstring 
            {
                
            int i, j;
                
            for(i = 0; i < 3; i ++)
                
            for(j = 0; j < 3; j ++)
                    tp_atos.s[i 
            * 3 + j] = arr[i][j] + '0';
                tp_atos.s[
            9= '\0';
            }

            int bfs()
            {
                cstring 
            as, ed;
                
            while(!q[0].empty()) q[0].pop();
                
            while(!q[1].empty()) q[1].pop();
                memset(h,
            0,sizeof(h));
                atos(sta, 
            as);
                atos(end, ed);
                
            if(nx(as% 2 != nx(ed) % 2return -1;//逆序奇偶性不同 
                q[0].push( as );
                q[
            1].push( ed );
                h[
            0][map( as )] = 1;
                h[
            1][map( ed )] = 1;
                
            if(h[0][map( ed )]) return 0;              //兩個(gè)相同 
                int index, size;
                step 
            = 0;
                cstring temp;
                
            while!q[0].empty() || !q[1].empty() )
                {
                    index 
            = 0;
                    
            if( q[0].size() > q[1].size() ) index = 1//取size小的先擴(kuò)展 
                    if( q[index].empty() ) index = 1 - index;
                    size 
            = q[index].size();
                    
            while(size --)
                    {
                        temp 
            = q[index].front();  
                        
            //temp.write();
                        q[index].pop();
                        
            if( extend(index, temp) ) return step + 1;  //擴(kuò)展 
                    }
                    step 
            ++;
                }
            }

            int main()
            {
                
            int ans = 0;
                read(sta);    
                read(end);
                ans 
            = bfs();
                printf(
            "%d\n",ans);
            }

            posted on 2009-08-22 20:27 superlong 閱讀(141) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            国产成年无码久久久免费| 亚洲国产精品婷婷久久| 久久妇女高潮几次MBA| 色婷婷综合久久久久中文一区二区| 亚洲av伊人久久综合密臀性色| 久久精品九九亚洲精品| 精品久久久久久无码中文野结衣| 91久久九九无码成人网站| 亚洲国产高清精品线久久| 久久久久高潮毛片免费全部播放| 精品久久久久久综合日本| 婷婷久久五月天| 国产精品久久久久乳精品爆 | 久久综合亚洲色HEZYO国产| 亚洲精品乱码久久久久久| 久久99精品久久久久久野外| 无码专区久久综合久中文字幕| 青青草原综合久久| 少妇人妻88久久中文字幕| 久久亚洲中文字幕精品一区四| 国产精品99久久精品| 亚洲综合熟女久久久30p| 久久夜色撩人精品国产| 69久久精品无码一区二区| 囯产极品美女高潮无套久久久 | 亚洲精品白浆高清久久久久久| 久久精品国产亚洲av瑜伽| 伊人久久大香线蕉影院95| 乱亲女H秽乱长久久久| 99久久免费国产精品特黄| 一本久久a久久精品亚洲| 欧美激情精品久久久久久| 色综合久久88色综合天天 | 久久亚洲AV成人出白浆无码国产| 亚洲国产婷婷香蕉久久久久久| 久久精品男人影院| 狠狠色丁香久久婷婷综| 四虎国产精品免费久久久| 中文精品久久久久国产网址 | 亚洲精品乱码久久久久久自慰| 久久毛片一区二区|