• <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 閱讀(604) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



9191精品国产免费久久|
久久强奷乱码老熟女网站
|
久久精品国产2020|
久久香综合精品久久伊人|
久久精品无码午夜福利理论片|
久久久久久久久无码精品亚洲日韩|
狼狼综合久久久久综合网|
国产精品伦理久久久久久|
久久强奷乱码老熟女网站|
色欲综合久久躁天天躁蜜桃|
精品国产乱码久久久久久人妻|
国内精品九九久久久精品|
日本精品久久久久影院日本|
人人狠狠综合88综合久久|
亚洲va久久久噜噜噜久久狠狠|
国产精品久久久久AV福利动漫|
久久精品免费一区二区三区|
久久久精品久久久久久|
激情伊人五月天久久综合|
97久久超碰国产精品旧版|
国产免费久久精品99re丫y|
99麻豆久久久国产精品免费|
亚洲精品乱码久久久久久不卡|
欧美va久久久噜噜噜久久|
日韩中文久久|
99久久精品费精品国产|
久久亚洲AV无码精品色午夜|
久久精品国产精品青草|
久久无码人妻一区二区三区|
久久综合视频网|
欧美成a人片免费看久久|
久久免费精品视频|
久久精品天天中文字幕人妻|
精品人妻伦九区久久AAA片69|
久久99国产一区二区三区|
久久香蕉国产线看观看乱码|
人妻无码αv中文字幕久久琪琪布|
亚洲精品午夜国产va久久|
久久亚洲av无码精品浪潮|
噜噜噜色噜噜噜久久|
久久乐国产综合亚洲精品|