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

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>
            
免费一级欧美片在线观看|
久久久美女艺术照精彩视频福利播放|
91久久精品久久国产性色也91|
夜夜嗨av一区二区三区四季av|
亚洲国产精品久久精品怡红院|
午夜一区二区三区在线观看|
性高湖久久久久久久久|
在线看片第一页欧美|
99国内精品久久|
美日韩精品免费观看视频|
国产日本欧美视频|
米奇777在线欧美播放|
亚洲网站啪啪|
欧美精品三级日韩久久|
欧美午夜在线观看|
亚洲电影毛片|
欧美日韩免费看|
免费观看久久久4p|
激情久久综艺|
亚洲大胆视频|
欧美日韩在线三级|
一区二区三区黄色|
亚洲精品视频在线播放|
先锋影音网一区二区|
亚洲自拍偷拍福利|
亚洲欧美日韩在线综合|
久久综合网色—综合色88|
在线日本欧美|
久久激情网站|
亚洲一区精品电影|
亚洲欧美日韩人成在线播放|
国产欧美一区在线|
亚洲精品偷拍|
久久精品中文字幕一区二区三区|
午夜精品一区二区三区在线|
欧美了一区在线观看|
亚洲毛片视频|
久久精品国产综合|
在线成人h网|
免费在线视频一区|
麻豆91精品|
欧美成人综合网站|
亚洲剧情一区二区|
国产亚洲精品aa午夜观看|
欧美一区二区三区播放老司机|
欧美一区二区视频97|
亚洲国产成人不卡|
久久国产日本精品|
9色精品在线|
玖玖视频精品|
日韩系列欧美系列|
久久精品盗摄|
欧美中文字幕在线播放|
欧美一区高清|
先锋影音国产一区|
一本色道88久久加勒比精品|
国产性天天综合网|
国产精品视频xxxx|
国产精品丝袜久久久久久app|
久久国产精品72免费观看|
久久久久久久一区|
狂野欧美一区|
亚洲欧美中文字幕|
亚洲欧美国产视频|
久久成人精品电影|
亚洲精品国偷自产在线99热|
久久久亚洲精品一区二区三区|
亚洲东热激情|
亚洲视频一起|
亚洲国产精品久久久久婷婷884|
国产精品乱人伦一区二区|
红桃视频亚洲|
99re6热只有精品免费观看|
国产婷婷色综合av蜜臀av|
亚洲国产成人av|
久久久久久有精品国产|
欧美一区2区视频在线观看
|
欧美日韩精品免费观看|
午夜精品视频|
欧美成在线视频|
国产乱人伦精品一区二区
|
欧美日韩一区二区三区四区在线观看
|
亚洲男人第一网站|
午夜精品久久久久久久99水蜜桃|
aa级大片欧美三级|
久久久人成影片一区二区三区观看
|
亚洲精品一区二区在线观看|
老司机久久99久久精品播放免费
|
一本色道久久综合亚洲精品不|
国产视频欧美|
国产精品久久久久久久久免费桃花|
国产综合网站|
亚洲精品亚洲人成人网|
国语自产精品视频在线看一大j8|
欧美成人精品激情在线观看
|
国产精品视频观看|
国外成人在线视频网站|
在线成人h网|
在线亚洲精品福利网址导航|
亚洲精品裸体|
亚洲三级电影全部在线观看高清|
校园春色国产精品|
国产精品久久久久99|
亚洲精品你懂的|
久久久久久网站|
久久久不卡网国产精品一区|
欧美1区3d|
雨宫琴音一区二区在线|
亚洲午夜国产成人av电影男同|
亚洲永久在线观看|
一区二区欧美日韩视频|
欧美高清不卡|
久久久久亚洲综合|
亚洲午夜小视频|
亚洲一区免费视频|
欧美一级淫片aaaaaaa视频|
影音先锋中文字幕一区二区|
中文久久乱码一区二区|
美女国内精品自产拍在线播放|
国产精品私拍pans大尺度在线|
亚洲精品女人|
亚洲一区二区精品|
aa亚洲婷婷|
欧美专区在线|
亚洲视频精选|
亚洲一级影院|
激情丁香综合|
久久婷婷av|
狼狼综合久久久久综合网|
亚洲老司机av|
欧美激情一区二区三区四区|
久久久久女教师免费一区|
久久人人爽人人爽爽久久|
亚洲图片欧美一区|
久久一区国产|
日韩天堂在线视频|
香蕉乱码成人久久天堂爱免费|
亚洲国产欧美一区二区三区久久|
亚洲婷婷免费|
日韩视频精品在线|
久久琪琪电影院|
欧美91精品|
亚洲视频观看|
欧美视频一区二区三区在线观看|
午夜在线精品偷拍|
国产精品一区视频|
亚洲黄页一区|
红桃视频国产精品|
欧美日韩综合视频|
国产一区观看|
欧美在线电影|
一本一本久久a久久精品综合妖精|
性刺激综合网|
久久青草久久|
欧美日韩国产天堂|
中日韩高清电影网|
欧美日精品一区视频|
久久午夜电影|
乱中年女人伦av一区二区|
亚洲精品乱码久久久久久蜜桃91|
亚洲国产综合91精品麻豆|
亚洲精品久久久久久久久久久久久|
欧美激情久久久久久|
亚洲在线电影|
欧美激情小视频|
亚洲欧美综合国产精品一区|
国产一区二区精品|
亚洲视频国产视频|
久久国产黑丝|
亚洲精品视频免费|
99在线|亚洲一区二区|
国产一区二区三区免费不卡|
国产日韩精品一区二区浪潮av|
一区二区三区日韩在线观看|
久久国产精品毛片|
日韩亚洲一区二区|
狠狠色狠狠色综合|
韩日欧美一区|
国产一区二三区|
欧美精品免费视频|
欧美激情一区在线|
欧美大学生性色视频|
9久re热视频在线精品|
蜜桃av一区|
亚洲理伦在线|
制服丝袜亚洲播放|
久久国产精品久久久久久|
免费h精品视频在线播放|
中日韩美女免费视频网址在线观看
|
国产亚洲精品激情久久|
国产精品一区二区在线|
韩日成人av|
亚洲性感美女99在线|
亚洲免费黄色|
免费亚洲一区|
黄色在线成人|
亚洲一区在线免费观看|
六月婷婷久久|
欧美日韩免费高清一区色橹橹|
国产午夜精品福利|