青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <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>
            
免费成人av在线|
在线观看视频一区二区|
欧美亚洲一级|
国产精品豆花视频|
亚洲综合色视频|
亚洲视频免费观看|
国产精品国内视频|
亚欧成人精品|
欧美淫片网站|
在线看国产一区|
亚洲欧洲综合|
美女日韩欧美|
一本大道av伊人久久综合|
亚洲日本在线观看|
av成人国产|
久久精品国产91精品亚洲|
欧美一区二区三区视频在线|
黄色亚洲在线|
亚洲高清一二三区|
欧美日韩亚洲一区二区三区在线|
亚洲欧美国产精品专区久久|
性一交一乱一区二区洋洋av|
激情五月婷婷综合|
亚洲日本成人网|
国产乱码精品一区二区三区五月婷
|
99re这里只有精品6|
国产精品一区亚洲|
蜜桃久久精品一区二区|
欧美日韩视频在线观看一区二区三区|
欧美一区二区视频免费观看
|
亚洲精品久久久久久久久|
欧美性生交xxxxx久久久|
久久精品视频在线观看|
欧美国产日韩亚洲一区|
午夜视频一区|
欧美欧美天天天天操|
久久成人一区|
欧美日韩综合视频网址|
久久综合中文|
国产精一区二区三区|
亚洲国产天堂网精品网站|
国产欧美日韩视频一区二区|
亚洲精品黄网在线观看|
1024亚洲|
久久精品国产精品亚洲精品|
亚洲午夜激情|
欧美国产日韩精品|
欧美大成色www永久网站婷|
亚洲欧美国产日韩天堂区|
日韩视频免费在线观看|
久久久久国产一区二区三区|
亚洲欧美中文日韩在线|
欧美绝品在线观看成人午夜影视|
久久一区亚洲|
国内综合精品午夜久久资源|
亚洲性人人天天夜夜摸|
在线亚洲一区观看|
欧美精品日韩精品|
欧美成人精品一区|
永久久久久久|
久久精品国产2020观看福利|
欧美中文字幕|
国产九九精品|
亚洲女同在线|
午夜精品理论片|
国产精品久久二区二区|
一区二区三区久久网|
一区二区精品在线|
欧美日韩午夜精品|
日韩午夜av|
亚洲一区精品在线|
国产精品女人毛片|
亚洲欧美激情四射在线日|
亚洲欧洲99久久|
国产日韩欧美在线视频观看|
亚洲素人在线|
久久精品国产v日韩v亚洲
|
在线观看三级视频欧美|
久久免费黄色|
欧美激情一区二区三区在线视频|
亚洲国产精品高清久久久|
免费欧美在线|
99精品99|
欧美一级午夜免费电影|
国内久久精品视频|
久久资源av|
日韩午夜在线电影|
午夜在线一区|
亚洲国产精品毛片|
欧美日本免费|
性欧美办公室18xxxxhd|
美女国内精品自产拍在线播放|
亚洲国产日日夜夜|
欧美人与禽猛交乱配|
亚洲资源av|
欧美激情视频一区二区三区免费
|
国产精品99久久久久久宅男
|
欧美激情在线|
亚洲女爱视频在线|
欧美xx69|
欧美一区二区成人|
亚洲激情视频|
国产精品伦一区|
另类尿喷潮videofree|
日韩图片一区|
男男成人高潮片免费网站|
中文有码久久|
亚洲国产小视频在线观看|
欧美视频在线一区|
久久先锋影音av|
亚洲图片激情小说|
在线亚洲观看|
亚洲大胆人体在线|
国产精品美女一区二区在线观看|
久久乐国产精品|
亚洲性色视频|
亚洲人精品午夜|
裸体丰满少妇做受久久99精品|
99这里只有久久精品视频|
韩国精品在线观看|
国产精品一区视频网站|
欧美日韩国产综合网|
久久亚洲精品一区|
亚洲综合激情|
9色精品在线|
91久久精品视频|
久久综合给合久久狠狠狠97色69|
亚洲欧美成人综合|
国产精品99久久久久久www|
亚洲激情在线|
在线观看欧美激情|
国产一区二区三区精品欧美日韩一区二区三区
|
欧美一区日韩一区|
亚洲综合好骚|
亚洲一区二区免费看|
亚洲精品久久久久久一区二区|
久久综合激情|
久久午夜羞羞影院免费观看|
午夜一区在线|
欧美一区二区在线免费播放|
亚洲一区亚洲二区|
亚洲一二三四区|
夜夜嗨av一区二区三区网站四季av
|
欧美激情视频一区二区三区免费|
久久免费精品视频|
久久亚洲风情|
美腿丝袜亚洲色图|
久久在线91|
久久综合999|
欧美精品久久一区二区|
欧美精品在线观看播放|
欧美日韩视频一区二区|
欧美午夜精品|
国产精品永久在线|
国产视频在线观看一区|
狠狠色香婷婷久久亚洲精品|
黄网动漫久久久|
亚洲精选成人|
亚洲女人天堂成人av在线|
欧美一区二区三区免费观看视频
|
亚洲高清毛片|
一区二区日韩|
午夜亚洲福利|
久久综合色一综合色88|
欧美黄色免费|
国产精品视频久久一区|
国产亚洲一区二区三区在线播放|
一区福利视频|
9久草视频在线视频精品|
午夜精品视频一区|
久久阴道视频|
亚洲精品乱码久久久久久久久|
亚洲国产日韩美|
亚洲免费成人av|
性欧美大战久久久久久久久|
亚洲欧美国产高清va在线播|
美国成人直播|
欧美日韩午夜激情|
黄色日韩网站视频|
91久久精品美女|
一级日韩一区在线观看|
久久久精品tv|
亚洲丁香婷深爱综合|
久久久久久久综合|
欧美激情va永久在线播放|
一区二区三区四区五区在线|
久久亚洲高清|
一区精品在线|
亚洲一区二区三区精品视频|
亚洲激情图片小说视频|
欧美一区1区三区3区公司|
亚洲第一综合天堂另类专|
亚洲久久视频|
久久免费视频网|
欧美午夜精品久久久久久久
|
欧美一区二区网站|
欧美激情2020午夜免费观看|
国产精品高精视频免费|
影音先锋久久久|
欧美综合二区|