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

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 1148 質數陣
		
            
		
            /*
            EOJ 1148 質數陣


            ----問題描述：

            在N*N的棋盤上(1<=N<=10)填入1,2,N*N共N*N個數,使得任意兩個相鄰的數之和為素數.
            例如,當N=2時,有
            1 2
            4 3


            ----輸入：

            每組測試數據一行,為一整數N(1<=N<=10)


            ----輸出：

            輸出滿足條件的最小序列的方案。
            最小序列即將每一行連接起來組成一行，然后使前面的盡可能小，當第一個數字相同時則比較下面一個，依次類推。
            比如當Ｎ＝２時，序列為1 2 4 3，當無滿足條件的方案時輸出"no answer"。


            ----樣例輸入：

            2


            ----樣例輸出：

            1 2
            4 3


            ----分析：

            深度優先搜索，
            從上往下，從左往右，依次確定每個位置的數字，
            確定某個位置的數字時，從小到大嘗試所有可用數字，
            優化方法，見代碼注釋。


            */


            /**********************************************************
            版本五：
            AC
            保存計算結果為字符串。
            */

            #include             <stdio.h>
            #include             <string.h>


            #define  N  14
            #define  N2 (N*N)
            int n, n2;

            #define  PL (N2*2)
            int isprime[ PL ];

            void init() {
                                int i, j;
                    memset( isprime,             0xff, sizeof(isprime) );
                    isprime[             0 ] = isprime[ 1 ] = 0;
                                for ( i = 2; i < PL; ++i ) {
                                        if ( isprime[ i ] ) {
                                                for ( j = i+i; j < PL; j += i ) {
                                            isprime[ j ]             = 0;
                                    }
                            }
                    }
            }


            struct  Cho
            {
                                int          num;
                                struct  Cho  *link;
            }            ;
            typedef              struct  Cho  Cho;

            Cho  cho[ N2             + 3 ];
            Cho              *headOdd, *headEven;
            int  num[ N ][ N ];

            char ans[ N ][ N2 * 4 ] = {0};

            void dfsInit() {
                                int i;
                                // 當 1 == n2 時，headEven 不會被使用
                    for ( i = 1; i <= n2; ++i ) {
                            cho[ i ].num             = i;
                            cho[ i ].link             = (cho + i + 2);
                    }
                    cho[ n2 ].link             = NULL;
                    cho[ n2            -1 ].link = NULL;
                    headOdd              = (cho + n2 + 1);
                    headEven             = (cho + n2 + 2);
                    headOdd            ->link  = (cho + 1);
                    headEven            ->link = (cho + 2);
            }

            int dfs( int i, int j ) {
                                int k, ni = i, nj = j+1;
                    Cho             *pre, *cur;
                                if ( nj >= n ) {
                            nj             = 0;
                                        ++ni;
                    }
                                // 左上角必然為數字 1 .
                    pre = ((((0<i)&&(num[i-1][j]&1)) || ((0<j)&&(num[i][j-1]&1))) ? headEven : headOdd);
                    cur             = pre->link;
                                while ( NULL != cur ) {
                            k             = cur->num;
                                        if (    ((0 == i)||(isprime[num[i-1][j]+k])) && 
                                    ((            0 == j)||(isprime[num[i][j-1]+k])) ) {
                                            num[ i ][ j ]             = k;
                                            pre            ->link = cur->link;

                                                        if ( (ni >= n) || (dfs(ni, nj)) ) {
                                                                return 1;
                                            }

                                            pre            ->link = cur;
                            }
                            pre             = cur;
                            cur             = pre->link;
                    }
                                return 0;
            }

            void search() {
                                if ( ans[ n ][ 0 ] ) {
                                        return;
                    }
                    dfsInit();
                                if ( dfs(0, 0) ) {
                                        int i, j;
                                        for ( i = 0; i < n; ++i ) {
                                    sprintf( ans[ n ]             + strlen(ans[n]), "%d", num[ i ][ 0 ] );
                                                for ( j = 1; j < n; ++j ) {
                                            sprintf( ans[ n ]             + strlen(ans[n]), " %d", num[ i ][ j ] );
                                    }
                                    sprintf( ans[ n ]             + strlen(ans[n]), "\n" );
                            }
                                        return;
                    }
                    sprintf( ans[ n ],             "no answer\n" );
                                return;
            }

            int main() {
                    init();
                                while ( 1 == scanf("%d", &n) ) {
                            n2             = n * n;
                            search();
                            printf(             "%s", ans[ n ] );
                    }
                                return 0;
            }


            /**********************************************************
            版本四：
            AC
            保存計算結果，避免重復計算。
            */
            /*
            #include <stdio.h>
            #include <string.h>


            #define  N  14
            #define  N2 (N*N)
            int n, n2;

            #define  PL (N2*2)
            int isprime[ PL ];
            int nprime, prime[ PL ];


            void init() {
                    int i, j;
                    memset( isprime, 0xff, sizeof(isprime) );
                    isprime[ 0 ] = isprime[ 1 ] = 0;
                    nprime = 0;
                    for ( i = 2; i < PL; ++i ) {
                            if ( isprime[ i ] ) {
                                    prime[ nprime++ ] = i;
                                    for ( j = i+i; j < PL; j += i ) {
                                            isprime[ j ] = 0;
                                    }
                            }
                    }
            }


            struct  Cho
            {
                    int          num;
                    struct  Cho  *link;
            };
            typedef  struct  Cho  Cho;

            Cho  cho[ N2 + 3 ];
            Cho  *headOdd, *headEven;
            int  num[ N ][ N ][ N ] = {0};

            void dfsInit() {
                    int i;
                    // 當 1 == n2 時，headEven 不會被使用
                    for ( i = 1; i <= n2; ++i ) {
                            cho[ i ].num = i;
                            cho[ i ].link = (cho + i + 2);
                    }
                    cho[ n2 ].link = NULL;
                    cho[ n2-1 ].link = NULL;
                    headOdd  = (cho + n2 + 1);
                    headEven = (cho + n2 + 2);
                    headOdd->link  = (cho + 1);
                    headEven->link = (cho + 2);
            }

            int dfs( int i, int j ) {
                    int k, ni = i, nj = j+1;
                    Cho *pre, *cur;
                    if ( nj >= n ) {
                            nj = 0;
                            ++ni;
                    }
                    // 左上角必然為數字 1 .
                    pre = ((((0<i)&&(num[n][i-1][j]&1)) || ((0<j)&&(num[n][i][j-1]&1))) ? headEven : headOdd);
                    cur = pre->link;
                    while ( NULL != cur ) {
                            k = cur->num;
                            if (    ((0 == i)||(isprime[num[n][i-1][j]+k])) && 
                                    ((0 == j)||(isprime[num[n][i][j-1]+k])) ) {
                                            num[ n ][ i ][ j ] = k;
                                            pre->link = cur->link;

                                            if ( (ni >= n) || (dfs(ni, nj)) ) {
                                                    return 1;
                                            }

                                            pre->link = cur;
                                            num[ n ][ i ][ j ] = 0;
                            }
                            pre = cur;
                            cur = pre->link;
                    }
                    return 0;
            }

            int search() {
                    if ( num[ n ][ 0 ][ 0 ] ) {
                            return 1; // 對無解的情況，未保存，會重復計算
                    }
                    dfsInit();
                    return dfs(0, 0);
            }

            int main() {
                    init();
                    while ( 1 == scanf("%d", &n) ) {
                            n2 = n * n;
                            if ( search() ) {
                                    int i, j;
                                    for ( i = 0; i < n; ++i ) {
                                            printf( "%d", num[ n ][ i ][ 0 ] );
                                            for ( j = 1; j < n; ++j ) {
                                                    printf( " %d", num[ n ][ i ][ j ] );
                                            }
                                            printf( "\n" );
                                    }
                            }
                            else {
                                    puts("no answer");
                            }
                    }
                    return 0;
            }
            */

            /**********************************************************
            版本三：
            TLE （對 9 == n 時太慢）
            備選鏈分奇偶。
            */
            /*
            #include <stdio.h>
            #include <string.h>


            #define  N  14
            #define  N2 (N*N)
            int n, n2;

            #define  PL (N2*2)
            int isprime[ PL ];
            int nprime, prime[ PL ];


            void init() {
                    int i, j;
                    memset( isprime, 0xff, sizeof(isprime) );
                    isprime[ 0 ] = isprime[ 1 ] = 0;
                    nprime = 0;
                    for ( i = 2; i < PL; ++i ) {
                            if ( isprime[ i ] ) {
                                    prime[ nprime++ ] = i;
                                    for ( j = i+i; j < PL; j += i ) {
                                            isprime[ j ] = 0;
                                    }
                            }
                    }
            }


            struct  Cho
            {
                    int          num;
                    struct  Cho  *link;
            };
            typedef  struct  Cho  Cho;

            Cho  cho[ N2 + 3 ];
            Cho  *headOdd, *headEven;
            int  num[ N ][ N ];

            void dfsInit() {
                    int i;
                    // 當 1 == n2 時，headEven 不會被使用
                    for ( i = 1; i <= n2; ++i ) {
                            cho[ i ].num = i;
                            cho[ i ].link = (cho + i + 2);
                    }
                    cho[ n2 ].link = NULL;
                    cho[ n2-1 ].link = NULL;
                    headOdd  = (cho + n2 + 1);
                    headEven = (cho + n2 + 2);
                    headOdd->link  = (cho + 1);
                    headEven->link = (cho + 2);
            }

            int dfs( int i, int j ) {
                    int k, ni = i, nj = j+1;
                    Cho *pre, *cur;
                    if ( nj >= n ) {
                            nj = 0;
                            ++ni;
                    }
                    // 左上角必然為數字 1 .
                    pre = ((((0<i)&&(num[i-1][j]&1)) || ((0<j)&&(num[i][j-1]&1))) ? headEven : headOdd);
                    cur = pre->link;
                    while ( NULL != cur ) {
                            k = cur->num;
                            if (    ((0 == i)||(isprime[num[i-1][j]+k])) && 
                                    ((0 == j)||(isprime[num[i][j-1]+k])) ) {
                                            num[ i ][ j ] = k;
                                            pre->link = cur->link;

                                            if ( (ni >= n) || (dfs(ni, nj)) ) {
                                                    return 1;
                                            }

                                            pre->link = cur;
                            }
                            pre = cur;
                            cur = pre->link;
                    }
                    return 0;
            }

            int search() {
                    dfsInit();
                    return dfs(0, 0);
            }

            int main() {
                    init();
                    while ( 1 == scanf("%d", &n) ) {
                            n2 = n * n;
                            if ( search() ) {
                                    int i, j;
                                    for ( i = 0; i < n; ++i ) {
                                            printf( "%d", num[ i ][ 0 ] );
                                            for ( j = 1; j < n; ++j ) {
                                                    printf( " %d", num[ i ][ j ] );
                                            }
                                            printf( "\n" );
                                    }
                            }
                            else {
                                    puts("no answer");
                            }
                    }
                    return 0;
            }
            */

            /**********************************************************
            版本二：
            TLE
            加入備選鏈優化。
            */
            /*
            #include <stdio.h>
            #include <string.h>


            #define  N  12
            #define  N2 (N*N)
            int n, n2;

            #define  PL (N2*2)
            int isprime[ PL ];
            int nprime, prime[ PL ];


            void init() {
                    int i, j;
                    memset( isprime, 0xff, sizeof(isprime) );
                    isprime[ 0 ] = isprime[ 1 ] = 0;
                    nprime = 0;
                    for ( i = 2; i < PL; ++i ) {
                            if ( isprime[ i ] ) {
                                    prime[ nprime++ ] = i;
                                    for ( j = i+i; j < PL; j += i ) {
                                            isprime[ j ] = 0;
                                    }
                            }
                    }
            }


            struct  Cho
            {
                    int          num;
                    struct  Cho  *link;
            };
            typedef  struct  Cho  Cho;

            Cho  cho[ N2 ];
            Cho  *head = NULL;
            int  num[ N ][ N ];

            void dfsInit() {
                    int i;
                    for ( i = 0; i <= n2; ++i ) {
                            cho[ i ].num = i;
                            cho[ i ].link = (cho + i + 1);
                    }
                    cho[ n2 ].link = NULL;
                    head = cho;
            }

            int dfs( int i, int j ) {
                    int k, ni = i, nj = j+1;
                    Cho *pre = head, *cur = head->link;
                    if ( nj >= n ) {
                            nj = 0;
                            ++ni;
                    }
                    while ( NULL != cur ) {
                            k = cur->num;
                            if (    ((0 == i)||(isprime[num[i-1][j]+k])) && 
                                    ((0 == j)||(isprime[num[i][j-1]+k])) ) {
                                            num[ i ][ j ] = k;
                                            pre->link = cur->link;

                                            if ( (ni >= n) || (dfs(ni, nj)) ) {
                                                    return 1;
                                            }

                                            pre->link = cur;
                            }
                            pre = cur;
                            cur = pre->link;
                    }
                    return 0;
            }

            int search() {
                    dfsInit();
                    return dfs(0, 0);
            }

            int main() {
                    init();
                    while ( 1 == scanf("%d", &n) ) {
                            n2 = n * n;
                            if ( search() ) {
                                    int i, j;
                                    for ( i = 0; i < n; ++i ) {
                                            printf( "%d", num[ i ][ 0 ] );
                                            for ( j = 1; j < n; ++j ) {
                                                    printf( " %d", num[ i ][ j ] );
                                            }
                                            printf( "\n" );
                                    }
                            }
                            else {
                                    puts("no answer");
                            }
                    }
                    return 0;
            }
            */


            /**********************************************************
            版本一：
            TLE

            樸素的 dfs 。
            */
            /*
            #include <stdio.h>
            #include <string.h>


            #define  N  12
            #define  N2 (N*N)
            int n, n2;

            #define  PL (N2*2)
            int isprime[ PL ];
            int nprime, prime[ PL ];


            void init() {
                    int i, j;
                    memset( isprime, 0xff, sizeof(isprime) );
                    isprime[ 0 ] = isprime[ 1 ] = 0;
                    nprime = 0;
                    for ( i = 2; i < PL; ++i ) {
                            if ( isprime[ i ] ) {
                                    prime[ nprime++ ] = i;
                                    for ( j = i+i; j < PL; j += i ) {
                                            isprime[ j ] = 0;
                                    }
                            }
                    }
            }

            int used[ N2 ], num[ N ][ N ];
            int dfs( int i, int j ) {
                    int k, ni = i, nj = j+1;
                    if ( nj >= n ) {
                            nj = 0;
                            ++ni;
                    }
                    for ( k = 1; k <= n2; ++k ) {
                            if ( (0 == used[ k ]) && 
                                    ((0 == i)||(isprime[num[i-1][j]+k])) && 
                                    ((0 == j)||(isprime[num[i][j-1]+k])) ) {
                                            num[ i ][ j ] = k;
                                            used[ k ] = 1;

                                            if ( (ni >= n) || (dfs(ni, nj)) ) {
                                                    return 1;
                                            }

                                            used[ k ] = 0;
                            }
                    }
                    return 0;
            }

            int search() {
                    memset( used, 0,sizeof(used) );
                    return dfs(0, 0);
            }

            int main() {
                    init();
                    while ( 1 == scanf("%d", &n) ) {
                            n2 = n * n;
                            if ( search() ) {
                                    int i, j;
                                    for ( i = 0; i < n; ++i ) {
                                            printf( "%d", num[ i ][ 0 ] );
                                            for ( j = 1; j < n; ++j ) {
                                                    printf( " %d", num[ i ][ j ] );
                                            }
                                            printf( "\n" );
                                    }
                            }
                            else {
                                    puts("no answer");
                            }
                    }
                    return 0;
            }
            */
            
		
            
			posted on 2012-04-21 16:59 coreBugZJ 閱讀(593) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



五月丁香综合激情六月久久|
中文字幕亚洲综合久久2|
久久精品亚洲日本波多野结衣|
久久人人爽人人爽人人av东京热|
亚洲&#228;v永久无码精品天堂久久|
久久se精品一区二区|
狠狠综合久久综合中文88
|
久久久久久久精品妇女99|
青青草原综合久久大伊人导航|
欧美麻豆久久久久久中文|
很黄很污的网站久久mimi色|
国产精品美女久久久久av爽|
热久久视久久精品18|
狠狠色丁香久久婷婷综|
亚洲va久久久噜噜噜久久狠狠|
91精品国产色综合久久|
久久久久人妻一区精品果冻|
久久久久久久精品妇女99|
99精品国产99久久久久久97|
国产三级观看久久|
色天使久久综合网天天|
日韩AV无码久久一区二区|
久久人人爽人爽人人爽av|
久久亚洲精品中文字幕|
国产精品一区二区久久国产|
国产精品久久久久蜜芽|
三级韩国一区久久二区综合|
久久青青草视频|
久久青青草原国产精品免费|
久久国产精品一国产精品金尊|
久久噜噜电影你懂的|
久久高清一级毛片|
久久丫精品国产亚洲av不卡|
AAA级久久久精品无码区|
久久久国产乱子伦精品作者|
久久国产精品-国产精品|
日韩精品久久久肉伦网站
|
一本色道久久综合狠狠躁篇
|
狠狠色婷婷久久一区二区|
99久久精品费精品国产|
青青草原综合久久大伊人|