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

            我希望你是我獨(dú)家記憶

            一段永遠(yuǎn)封存的記憶,隨風(fēng)而去
            posts - 263, comments - 31, trackbacks - 0, articles - 3
               :: 首頁(yè) :: 新隨筆 ::  :: 聚合  :: 管理

            USACO_523 DFS

            Posted on 2009-10-14 16:44 Hero 閱讀(256) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 代碼如詩(shī)--ACM
              1 /*
              2 TASK: wissqu
              3 LANG: C++
              4 
              5       Compiling
              6 Compile: OK
              7 
              8          Executing
              9          Test 1: TEST OK [3.305 secs, 2808 KB]
             10 
             11       All tests OK.
             12 */
             13 #include <stdio.h>
             14 #include <string.h>
             15 
             16 const int size = 1000 ;
             17 
             18 char instr[100] ;
             19 int data[6][6] ;
             20 int flag[6][6] ;
             21 int cownum[10] ;
             22 int restemp[4][20] ;
             23 int result[4][20] ;
             24 int resnum ;
             25 
             26 void input()
             27 {
             28     memset( data, 0sizeof(data) ) ;
             29     memset( cownum, 0sizeof(cownum) ) ;
             30 
             31     forint i=1; i<=4; i++ )
             32     {
             33         scanf( "%s"&instr ) ;
             34         forint j=0; j<4; j++ )
             35         {
             36             data[i][j+1= instr[j] - 'A' + 1 ;
             37             cownum[data[i][j+1]]++ ;
             38         }
             39     }
             40 
             41     cownum[3]-- ; cownum[4]++ ;
             42 }
             43 
             44 bool checkposi( int cowtype, int row, int col )
             45 {
             46     if( row<1 || row >4 || col<1 || col>4 ) return false ;
             47     if( flag[row][col] ) return false ;
             48 
             49     if( cowtype == data[row][col] ) return false ;
             50     if( cowtype == data[row][col-1] ) return false ;
             51     if( cowtype == data[row][col+1] ) return false ;
             52 
             53     if( cowtype == data[row-1][col] ) return false ;
             54     if( cowtype == data[row-1][col-1] ) return false ;
             55     if( cowtype == data[row-1][col+1] ) return false ;
             56 
             57     if( cowtype == data[row+1][col] ) return false ;
             58     if( cowtype == data[row+1][col-1] ) return false ;
             59     if( cowtype == data[row+1][col+1] ) return false ;
             60 
             61     return true ;
             62 }
             63 
             64 void frescpy() 
             65 {
             66     forint i=0; i<=2; i++ )
             67     {
             68         forint j=0; j<=16; j++ )
             69         {
             70             result[i][j] = restemp[i][j] ;
             71         }
             72     }
             73 }
             74 void fresult()
             75 {
             76     resnum = resnum + 1 ;
             77     if( resnum == 1 ) memcpy( result, restemp, sizeof(result) ) ;
             78 
             79     forint i=0; i<=2; i++ )
             80     {
             81         forint j=0; j<=15; j++ )
             82         {
             83             if( restemp[i][j] < result[i][j] )
             84             {
             85                 //memcpy( result, restemp, sizeof(result) ) ;
             86                 return ;
             87             }
             88         }
             89     }
             90 }
             91 void DFS( int cowtype, int row, int col, int step )
             92 {
             93     //printf( "step == %d tpye = %d row=%d col=%d\n", step, cowtype, row, col ) ;
             94 
             95     if( row<1 || row >4 || col<1 || col>4 ) return ;
             96     if( step > 15 ) return ;
             97     if( flag[row][col] ) return ;
             98     if( cownum[cowtype]<=0 ) return ;
             99     if!checkposi( cowtype, row, col ) ) return ;
            100 
            101     int temp = data[row][col] ;
            102     data[row][col] = cowtype ;
            103     flag[row][col] = 1 ;
            104     cownum[cowtype]-- ;
            105 
            106     restemp[0][step] = cowtype ;
            107     restemp[1][step] = row ;
            108     restemp[2][step] = col ;
            109 
            110     //if( step >=13 )
            111         //printf( "step == %d tpye = %d row=%d col=%d\n", step, cowtype, row, col ) ;
            112     if( step == 15 )    
            113     {
            114         fresult() ;
            115     }
            116     else
            117     {
            118         forint type=1; type<=5; type++ )
            119         {
            120             if( cownum[type] <= 0 ) continue ; 
            121             forint r=1; r<=4; r++ )
            122             {
            123                 forint c=1; c<=4; c++ )
            124                 {
            125                     if( flag[r][c] ) continue ;
            126                     //for( int type=1; type<=5; type++ )
            127                     {
            128                         //if( cownum[type] <= 0 ) continue ;
            129                         DFS( type, r, c, step+1 ) ;
            130                     }
            131                 }
            132             }
            133         }
            134     }
            135 
            136     data[row][col] = temp ;
            137     flag[row][col] = 0 ;
            138     cownum[cowtype]++ ;
            139 }
            140 
            141 void solve()
            142 {
            143     resnum = 0 ;
            144     memset( flag, 0sizeof(flag) ) ;
            145 
            146     forint i=0; i<=2; i++ ) forint j=0; j<=16; j++ ) result[i][j] = 9 ;
            147 
            148     forint r=1; r<=4; r++ )
            149     {
            150         forint c=1; c<=4; c++ )
            151         {
            152             DFS( 4, r, c, 0 ) ;
            153         }
            154     }
            155 }
            156 
            157 void output()
            158 {
            159     forint i=0; i<=15; i++ )
            160     {
            161         printf( "%c %d %d\n", result[0][i]+'A'-1, result[1][i], result[2][i] ) ;
            162     }
            163     printf( "%d\n", resnum ) ;
            164 }
            165 
            166 int main()
            167 {
            168     freopen( "wissqu.in""r", stdin ) ;
            169     freopen( "wissqu.out","w",stdout ) ;
            170 
            171     input() ;
            172 
            173     solve() ;
            174 
            175     output() ;
            176 
            177     return 0 ;
            178 }
            179 
            180 
            午夜天堂av天堂久久久| 亚洲午夜精品久久久久久浪潮| 中文精品久久久久人妻| 久久人人爽人人爽人人片AV麻豆| 久久精品桃花综合| 久久精品国产亚洲AV无码娇色| 色播久久人人爽人人爽人人片aV| 狠狠色婷婷久久综合频道日韩| 99久久国产免费福利| 久久发布国产伦子伦精品| 亚洲国产精品久久久久婷婷软件 | 2021国产成人精品久久| 老司机午夜网站国内精品久久久久久久久 | 国产—久久香蕉国产线看观看 | 丁香五月网久久综合| 久久人人爽人人爽人人片av高请| 久久亚洲电影| 久久成人精品视频| 久久线看观看精品香蕉国产| 国产成人久久精品激情| 国产产无码乱码精品久久鸭| 三级片免费观看久久| 国产成人久久激情91| 色8久久人人97超碰香蕉987| 一级做a爰片久久毛片免费陪| 久久久久久综合一区中文字幕 | 色综合久久88色综合天天 | 91久久精品电影| 久久久久四虎国产精品| 国产亚洲精久久久久久无码| 亚洲精品乱码久久久久久按摩| 亚洲国产成人久久综合野外| 久久综合伊人77777| 亚洲国产成人久久综合野外| 久久久黄色大片| 亚洲七七久久精品中文国产| 国产精品久久久久久久app | 亚洲第一永久AV网站久久精品男人的天堂AV | 久久精品综合一区二区三区| 亚洲精品无码久久久| 久久男人中文字幕资源站|