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

            pku2133 Cow Imposters BFS

            題意:
            FJ給每個牛一個號碼牌,牛不喜歡這個號碼牌,就私自建立了1個機器用2個號碼牌來生成一個新號碼牌(兩個輸入口可以放一個號碼牌并且不消耗號碼牌),問最少使用的步數達到新號碼(或者達到最優號碼,N多關鍵字排序規則,一看就知道搜索)。


            解法&代碼
            BFS,直接看代碼吧。。
             1 Source Code
             2 
             3 Problem: 2133        User: yzhw
             4 Memory: 660K        Time: 0MS
             5 Language: C++        Result: Accepted
             6 Source Code
             7 # include <cstdio>
             8 # include <cstring>
             9 # include <stack>
            10 # include <cstdlib>
            11 using namespace std;
            12 int used[1<<16];
            13 int q[1<<16],s=0,e=-1;
            14 int toInt(char *str)
            15 {
            16     int res=0;
            17     for(int i=0;str[i]!='\0';i++)
            18       res=res*2+str[i]-48;
            19     return res;
            20 }
            21 
            22 void print(int top,int b)
            23 {
            24          stack<int> ans;
            25           for(int i=0;i<b;i++)
            26           {
            27             ans.push(top%2);
            28             top/=2;
            29           }
            30           while(!ans.empty())
            31           {
            32             printf("%d",ans.top());
            33             ans.pop();
            34           }
            35           printf("\n");
            36 }
            37 int diff(int target,int code,int b)
            38 {
            39     int ans=0;
            40     for(int i=0;i<b;i++)
            41     {
            42        ans+=(target%2!=code%2);
            43        target/=2;
            44        code/=2;
            45     }
            46     return ans;
            47 }
            48 int main()
            49 {
            50    // freopen("ans.txt","w",stdout);
            51    // int pre[1<<16][2];
            52     memset(used,0,sizeof(used));
            53     int b,ee;
            54     scanf("%d%d",&b,&ee);
            55     char str[20];
            56     scanf("%s",str);
            57     int target=toInt(str);
            58     for(int i=0;i<ee;i++)
            59     {
            60        scanf("%s",str);
            61        q[++e]=toInt(str);
            62     }
            63     while(s<=e)
            64     {
            65        int top=q[s++];
            66        //print(top,b);
            67       // printf("%d %d %d %d\n",top,pre[top][0],pre[top][1],used[top]);
            68        //system("pause");
            69        if(top==target&&used[top])
            70        {
            71           printf("%d\n",used[top]);
            72           print(top,b);
            73           //system("pause");
            74           return 0;
            75        }
            76        for(int i=0;i<ee;i++)
            77          if(!used[top^q[i]])
            78            used[top^q[i]]=used[top]+1,q[++e]=(top^q[i]);
            79     }
            80     int bestcode,bestdiff=0xfffffff,beststep;
            81     for(int i=0;i<(1<<b);i++)
            82       if(used[i]&&(diff(i,target,b)<bestdiff||diff(i,target,b)==bestdiff&&used[i]<beststep||diff(i,target,b)==bestdiff&&used[i]==beststep&&i<bestcode))
            83          bestcode=i,bestdiff=diff(i,target,b),beststep=used[i];
            84     printf("%d\n",beststep);
            85     print(bestcode,b);
            86     //system("pause");
            87     return 0;
            88     
            89 }

            posted on 2011-03-13 02:27 yzhw 閱讀(259) 評論(0)  編輯 收藏 引用 所屬分類: search

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久99亚洲网美利坚合众国| 国产无套内射久久久国产| 久久精品免费全国观看国产| 亚洲伊人久久成综合人影院 | 久久久久高潮综合影院| 伊人久久成人成综合网222| 久久久噜噜噜久久中文字幕色伊伊 | 国产69精品久久久久99尤物| 久久久网中文字幕| 欧美熟妇另类久久久久久不卡| 91精品国产91久久久久久青草| 亚洲国产成人乱码精品女人久久久不卡 | 国产精品久久久久久久久免费| 久久久精品久久久久久| 久久精品人人做人人妻人人玩| 亚洲国产天堂久久综合网站| 中文无码久久精品| 久久嫩草影院免费看夜色| 国产精品美女久久久久久2018| 性做久久久久久久久久久| 中文精品久久久久国产网址| 香蕉久久夜色精品升级完成| 久久无码国产| 久久精品一区二区三区中文字幕| 久久久久国产精品熟女影院| 久久久久人妻一区二区三区| 日韩美女18网站久久精品| 97久久精品人人澡人人爽| 久久AV高清无码| 国产激情久久久久久熟女老人| 精品久久人人做人人爽综合 | 亚洲午夜无码AV毛片久久| 久久久久国产精品麻豆AR影院| 国产成人99久久亚洲综合精品| AAA级久久久精品无码片| 国产精品美女久久久久久2018 | 久久精品嫩草影院| 久久婷婷国产麻豆91天堂| 青青草国产精品久久久久| 久久精品国产91久久麻豆自制| 国产成人久久精品区一区二区|