• <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 質(zhì)數(shù)陣
		
            
		
            /*
            EOJ 1148 質(zhì)數(shù)陣


            ----問題描述：

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


            ----輸入：

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


            ----輸出：

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


            ----樣例輸入：

            2


            ----樣例輸出：

            1 2
            4 3


            ----分析：

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


            */


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

            #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;
                                // 當(dāng) 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;
                    }
                                // 左上角必然為數(shù)字 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
            保存計算結(jié)果，避免重復(fù)計算。
            */
            /*
            #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;
                    // 當(dāng) 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;
                    }
                    // 左上角必然為數(shù)字 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; // 對無解的情況，未保存，會重復(fù)計算
                    }
                    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;
                    // 當(dāng) 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;
                    }
                    // 左上角必然為數(shù)字 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
            加入備選鏈優(yōu)化。
            */
            /*
            #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 閱讀(613) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



日本久久中文字幕|
无码人妻精品一区二区三区久久久|
国产V亚洲V天堂无码久久久|
青青青国产成人久久111网站|
99热都是精品久久久久久|
热综合一本伊人久久精品|
久久综合给久久狠狠97色
|
久久免费香蕉视频|
久久精品成人欧美大片|
嫩草影院久久99|
99久久免费国产精品特黄|
青青草原综合久久|
亚洲精品tv久久久久久久久
|
久久婷婷人人澡人人|
人妻久久久一区二区三区|
狠狠色丁香婷婷综合久久来来去|
亚洲精品无码成人片久久|
午夜肉伦伦影院久久精品免费看国产一区二区三区
|
久久精品日日躁夜夜躁欧美|
丁香五月综合久久激情|
三上悠亚久久精品|
少妇人妻综合久久中文字幕|
久久精品一区二区影院|
国产一级持黄大片99久久|
亚洲伊人久久精品影院|
伊人 久久 精品|
少妇被又大又粗又爽毛片久久黑人|
国产精品久久久久影院嫩草|
久久天天躁狠狠躁夜夜avapp|
老男人久久青草av高清|
中文国产成人精品久久亚洲精品AⅤ无码精品|
72种姿势欧美久久久久大黄蕉|
熟妇人妻久久中文字幕|
亚洲色大成网站WWW久久九九|
久久99久国产麻精品66|
中文精品99久久国产|
国产亚洲美女精品久久久2020|
久久人做人爽一区二区三区|
狠狠色丁香婷婷久久综合|
久久青青草视频|
一本一本久久A久久综合精品|