• <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 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



国产精品美女久久久m|
精品久久久久久综合日本|
久久影视综合亚洲|
欧美粉嫩小泬久久久久久久
|
久久久久亚洲精品日久生情|
日韩人妻无码一区二区三区久久99
|
色诱久久久久综合网ywww|
成人久久久观看免费毛片|
国产视频久久|
亚洲精品无码久久久久久|
久久成人精品视频|
热RE99久久精品国产66热|
久久久久久国产精品免费无码|
99久久国产综合精品五月天喷水|
日产久久强奸免费的看|
国产成人精品白浆久久69|
亚洲国产天堂久久综合|
久久精品www|
2021久久国自产拍精品|
久久国产免费|
国产精品久久久久国产A级|
欧美日韩精品久久久免费观看|
久久久久人妻一区精品性色av|
欧美性猛交xxxx免费看久久久|
国产成人精品久久二区二区|
久久久国产视频|
久久久久久国产a免费观看不卡
|
久久久久人妻一区二区三区|
亚洲一区二区三区日本久久九|
久久久久免费看成人影片|
久久精品国产欧美日韩99热|
久久久精品国产Sm最大网站|
精品亚洲综合久久中文字幕|
69久久精品无码一区二区|
日本久久久久亚洲中字幕|
2021国内久久精品|
欧美一级久久久久久久大片|
国产精品免费久久久久影院|
国产精品嫩草影院久久|
久久这里只精品国产99热|
久久狠狠色狠狠色综合|