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

            Problem description

            Now an emergent task for you is to open a password lock. The password is consisted of four digits. Each digit is numbered from 1 to 9.
            Each time, you can add or minus 1 to any digit. When add 1 to '9', the digit will change to be '1' and when minus 1 to '1', the digit will change to be '9'. You can also exchange the digit with its neighbor. Each action will take one step.

            Now your task is to use minimal steps to open the lock.

            Note: The leftmost digit is not the neighbor of the rightmost digit.


            ?
            Input
            The input file begins with an integer T, indicating the number of test cases.

            Each test case begins with a four digit N, indicating the initial state of the password lock. Then followed a line with anotther four dight M, indicating the password which can open the lock. There is one blank line after each test case.


            ?
            Output
            For each test case, print the minimal steps in one line.


            Sample Input
            2
            1234
            2144

            1111
            9999
            ?
            Sample Output
            2
            4




            廣度搜索:

            ??1 #include? < iostream >
            ??2 #include? < queue >
            ??3 #include? < algorithm >
            ??4
            ??5 using ? namespace ?std;
            ??6
            ??7 bool ??mark[ 10000 ];
            ??8
            ??9 struct ?Node
            ?10 {
            ?11 ???? int ???step;
            ?12 ???? char ??state[ 5 ];
            ?13
            ?14 ????Node()
            ?15 ???? {}
            ?16
            ?17 ????Node(? int ?i,? char * ?str?)
            ?18 ????????:step(i)
            ?19 ???? {
            ?20 ????????strcpy(?state,?str?);
            ?21 ????}

            ?22 }
            ;
            ?23
            ?24
            ?25 int ?getn(? char ?str[ 5 ]?)
            ?26 {
            ?27 ???? return ?(str[ 0 ] - ? ' 0 ' ) * ? 1000 + ?(?str[ 1 ] - ? ' 0 ' ?) * ? 100 + ?(?str[ 2 ] - ? ' 0 ' ?) * ? 10 + ?(str[ 3 ] - ? ' 0 ' ?);
            ?28 }

            ?29
            ?30
            ?31 int ?main()
            ?32 {
            ?33 ???? char ????initial[ 5 ];
            ?34 ???? char ????open[ 5 ];
            ?35 ???? int ?????Cases;
            ?36
            ?37 ????scanf( " %d " , & Cases);
            ?38 ???? while ?(?Cases -- ?)
            ?39 ???? {
            ?40 ????????memset(?mark,? false ,? sizeof (mark)?);
            ?41
            ?42 ????????queue < struct ?Node > ??q;
            ?43 ????????scanf( " %s%s " ,initial,open);
            ?44
            ?45 ????????q.push?(?Node( 0 ,initial)?);
            ?46 ????????mark[?getn(initial)?] = ? true ;
            ?47
            ?48 ???????? while ?(? ! q.empty?()?)
            ?49 ???????? {
            ?50 ???????????? struct ?Node?head = ?q.front?();
            ?51 ????????????q.pop?();
            ?52
            ?53 ???????????? if ?(?strcmp(?head.state?,?open) == ? 0 ?)
            ?54 ???????????? {
            ?55 ????????????????printf( " %d " ,head.step?);
            ?56 ???????????????? break ;
            ?57 ????????????}

            ?58
            ?59 ???????????? for ?(? int ?i = ? 0 ;?i < ? 3 ;? ++ i?)
            ?60 ???????????? {????????
            ?61 ???????????????? char ?temp[ 5 ];
            ?62 ????????????????strcpy(?temp,?head.state?);
            ?63
            ?64 ????????????????std::swap?(?temp[i],?temp[i + 1 ]?);
            ?65 ???????????????? if ?(? ! mark[?getn(temp)?]?)
            ?66 ???????????????? {
            ?67 ????????????????????q.push?(?Node(head.step + ? 1 ,?temp?)?);
            ?68 ????????????????????mark[?getn(temp)?] = ? true ;
            ?69 ????????????????}

            ?70 ????????????}

            ?71
            ?72 ???????????? for ?(? int ?i = ? 0 ;?i < ? 4 ;? ++ i?)
            ?73 ???????????? {
            ?74 ???????????????? char ?temp[ 5 ];
            ?75 ????????????????strcpy(?temp,?head.state?);
            ?76
            ?77 ???????????????? if ?(?temp[i] == ? ' 9 ' ?)?temp[i] = ? ' 1 ' ;
            ?78 ???????????????? else ?temp[i] = ?temp[i] + ? 1 ;
            ?79
            ?80 ???????????????? int ?n = ?getn(temp);
            ?81 ???????????????? if ?(? ! mark[n]?)
            ?82 ???????????????? {
            ?83 ????????????????????q.push?(?Node(?head.step + ? 1 ,?temp?)?);
            ?84 ????????????????????mark[n] = ? true ;
            ?85 ????????????????}

            ?86 ????????????}

            ?87
            ?88 ???????????? for ?(? int ?i = ? 0 ;?i < ? 4 ;? ++ i?)
            ?89 ???????????? {
            ?90 ???????????????? char ?temp[ 5 ];
            ?91 ????????????????strcpy(?temp,?head.state?);
            ?92
            ?93 ???????????????? if ?(?temp[i] == ? ' 1 ' ?)?temp[i] = ? ' 9 ' ;
            ?94 ???????????????? else ?temp[i] = ?temp[i] - ? 1 ;
            ?95
            ?96 ???????????????? int ?n = ?getn(temp);
            ?97 ???????????????? if ?(? ! mark[n]?)
            ?98 ???????????????? {
            ?99 ????????????????????q.push?(?Node(?head.step + ? 1 ,?temp?)?);
            100 ????????????????????mark[n] = ? true ;
            101 ????????????????}

            102 ????????????}

            103 ????????}

            104
            105 ???????? if ?(?Cases?)?printf( " \n " );
            106 ????}

            107
            108 ???? return ? 0 ;
            109 }

            110
            posted on 2008-08-19 16:38 Darren 閱讀(427) 評論(0)  編輯 收藏 引用 所屬分類: 搜索
            国产亚洲美女精品久久久| 精品九九久久国内精品| 日本欧美久久久久免费播放网| 久久av高潮av无码av喷吹| 99久久成人18免费网站| 精品无码久久久久久久久久| 久久人妻少妇嫩草AV蜜桃| 国产精品九九九久久九九| 亚洲精品国精品久久99热| 日韩乱码人妻无码中文字幕久久| 久久亚洲春色中文字幕久久久| 久久精品国产第一区二区三区| 热综合一本伊人久久精品| 久久A级毛片免费观看| 久久精品成人影院| 2021久久国自产拍精品| 日本高清无卡码一区二区久久 | 久久综合精品国产二区无码| 国产高潮国产高潮久久久| 亚洲国产成人精品久久久国产成人一区二区三区综 | 狠狠色丁香久久综合五月| 亚洲精品乱码久久久久久不卡| 久久午夜羞羞影院免费观看| 青草久久久国产线免观| 久久久综合九色合综国产| 伊人久久大香线蕉av一区| 久久无码国产| 久久国产精品99精品国产987| 久久精品久久久久观看99水蜜桃| 欧美成a人片免费看久久| 2020久久精品国产免费| 日日噜噜夜夜狠狠久久丁香五月| 久久亚洲高清综合| 国产精品欧美久久久久天天影视| 精品国产婷婷久久久| 久久精品成人免费网站| 国产午夜精品久久久久免费视| 99久久做夜夜爱天天做精品| 一本一道久久综合狠狠老| 久久综合久久综合亚洲| 欧美va久久久噜噜噜久久|