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





            
	    
    




            






            

				

            


    
    







            
	   
	



热久久国产精品|
亚洲精品tv久久久久久久久|
亚洲国产精品久久久久婷婷软件|
精品久久久久久久久中文字幕|
91精品国产91热久久久久福利
|
久久久久久国产a免费观看不卡|
亚洲AV伊人久久青青草原|
国产激情久久久久久熟女老人|
亚洲国产精品久久久久|
国产激情久久久久久熟女老人|
国产午夜精品久久久久九九|
一本一本久久a久久综合精品蜜桃|
丁香久久婷婷国产午夜视频|
亚洲AV无码久久精品蜜桃|
久久精品无码一区二区三区免费|
久久免费看黄a级毛片|
蜜臀久久99精品久久久久久
|
香蕉久久一区二区不卡无毒影院|
精品久久久久久久国产潘金莲|
国产视频久久|
99久久www免费人成精品|
国产精品久久久久久福利漫画|
精品久久久久久久久免费影院|
色婷婷噜噜久久国产精品12p|
国内精品伊人久久久久|
久久这里只有精品18|
久久久久久国产精品美女|
热RE99久久精品国产66热|
久久996热精品xxxx|
久久丝袜精品中文字幕|
亚洲狠狠久久综合一区77777
|
77777亚洲午夜久久多喷|
久久亚洲精精品中文字幕|
天堂久久天堂AV色综合|
亚洲中文久久精品无码|
久久香综合精品久久伊人|
国产精品久久久亚洲|
亚洲午夜久久久精品影院
|
久久精品嫩草影院|
国产99久久九九精品无码|
久久久久久av无码免费看大片|