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

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在线播放|
欧美日韩在线视频一区|
午夜精品久久久99热福利|
先锋影音网一区二区|
在线欧美视频|
av不卡免费看|
亚洲国产成人av|
亚洲一区二区三区色|
永久555www成人免费|
亚洲精品一区在线|
国产一区香蕉久久|
亚洲人成艺术|
国产日韩欧美自拍|
日韩网站在线看片你懂的|
国产一区91|
一区二区三区三区在线|
亚洲激情社区|
欧美主播一区二区三区美女 久久精品人|
精品成人一区二区三区|
在线视频你懂得一区|
亚洲欧洲精品一区二区三区|
欧美影院成人|
欧美一二三区精品|
欧美国产第二页|
久久综合狠狠综合久久综青草|
欧美日韩亚洲激情|
亚洲国产高清一区|
亚洲国产精品黑人久久久|
午夜久久99|
亚洲男人av电影|
欧美日韩国产在线播放网站|
欧美成人黄色小视频|
国语精品中文字幕|
亚洲一品av免费观看|
亚洲国产经典视频|
经典三级久久|
香蕉av777xxx色综合一区|
亚洲男人的天堂在线观看|
欧美日韩免费观看一区二区三区|
免费视频久久|
一色屋精品视频在线看|
久久成人18免费网站|
久久精品视频va|
国产亚洲精品福利|
欧美亚洲在线观看|
久久精品中文|
黄色一区二区在线|
久久久精品日韩欧美|
久久人人爽国产|
黄色成人小视频|
久久久久久九九九九|
久久视频在线免费观看|
激情丁香综合|
欧美 日韩 国产在线|
免费成人小视频|
亚洲国产清纯|
欧美精品亚洲二区|
一区二区三区精品视频|
亚洲婷婷综合久久一本伊一区|
欧美三级网页|
午夜精品视频一区|
快播亚洲色图|
亚洲国产美国国产综合一区二区|
老司机67194精品线观看|
女生裸体视频一区二区三区|
亚洲高清视频在线观看|
欧美成人三级在线|
亚洲视频在线看|
欧美一级一区|
影音先锋亚洲一区|
欧美成ee人免费视频|
99精品欧美一区|
欧美在线视屏|
亚洲国产女人aaa毛片在线|
欧美激情四色|
一本色道久久99精品综合|
亚洲欧美国产视频|
国产欧美一区二区色老头|
久久蜜桃av一区精品变态类天堂|
欧美成人一区二区三区在线观看
|
亚洲欧美中日韩|
国产自产高清不卡|
欧美mv日韩mv国产网站app|
亚洲精品一区在线|
久久免费99精品久久久久久|
亚洲精品久久久久久久久久久|
国产精品va在线播放|
久久久久高清|
一区二区欧美日韩视频|
久久人人97超碰国产公开结果
|
亚洲视频一区二区在线观看|
亚洲欧美日韩精品久久久久|
一区二区在线观看视频|
欧美三级在线视频|
久久久伊人欧美|
亚洲午夜av电影|
国产亚洲观看|
欧美在线日韩在线|
亚洲五月六月|
伊人久久亚洲美女图片|
欧美视频在线观看|
久久久国产精品一区|
中文av一区特黄|
亚洲黄色成人|
裸体歌舞表演一区二区|
亚洲制服少妇|
亚洲人成网站777色婷婷|
国产欧美日韩伦理|
欧美日韩午夜在线视频|
久久一区国产|
欧美在线观看一区|
亚洲自拍都市欧美小说|
亚洲三级电影在线观看|
老司机午夜精品|
久久精品久久99精品久久|
亚洲一区三区在线观看|
亚洲日本视频|
在线欧美电影|
在线成人激情黄色|
国产一区二区三区四区老人|
国产精品黄视频|
国产精品电影在线观看|
欧美日韩国产综合网|
欧美日本国产视频|
欧美激情亚洲另类|
欧美xart系列高清|
欧美亚洲综合久久|
午夜精品国产更新|
亚洲在线视频网站|
亚洲小说欧美另类婷婷|
亚洲开发第一视频在线播放|
亚洲国产成人一区|
欧美成人免费观看|
欧美电影免费观看高清|
欧美成人免费网|
欧美激情一区二区三区高清视频|
麻豆精品视频在线|
欧美成人精品一区|
欧美夫妇交换俱乐部在线观看|
蜜桃精品久久久久久久免费影院|
久久久一区二区|
免费av成人在线|
亚洲第一福利在线观看|
亚洲激情精品|
夜夜嗨av色综合久久久综合网|
亚洲免费观看视频|
亚洲视频久久|
欧美亚洲午夜视频在线观看|
欧美一区二区三区另类|
欧美一级午夜免费电影|
久久国产婷婷国产香蕉|
狼人社综合社区|
欧美日韩国产美女|
国产精品免费看片|
国产一区二区三区在线观看精品|
激情综合久久|
亚洲激情网站免费观看|
亚洲精品久久久蜜桃|
一本色道久久88综合亚洲精品ⅰ
|
一二三区精品|
午夜精品在线观看|
久久久亚洲国产美女国产盗摄|
美日韩精品免费观看视频|
欧美成人有码|
欧美性猛交99久久久久99按摩|
欧美日韩国产123|
欧美日韩另类在线|
国产日韩一区二区三区在线|
在线看片一区|
亚洲视频精选在线|
久久精品中文字幕免费mv|
欧美大片免费观看在线观看网站推荐|
欧美激情一区在线|
久久精品一区二区三区四区|
久久夜色精品亚洲噜噜国产mv
|
久久久国产一区二区三区|
久久资源av|
亚洲国产视频一区|
欧美日韩一级大片网址|
亚洲欧美第一页|
久久只有精品|
夜夜嗨av一区二区三区中文字幕
|
国产午夜久久|
农夫在线精品视频免费观看|
中文国产一区|
免费久久精品视频|
欧美一级二区|
亚洲精品国偷自产在线99热|
国产精品久久久久久久免费软件|
久久亚洲精品网站|
亚洲欧美在线一区二区|
亚洲日韩第九十九页|
亚洲综合电影一区二区三区|
亚洲风情亚aⅴ在线发布|
国产毛片精品视频|
欧美理论电影网|
老司机午夜精品|
久久精品麻豆|
欧美在线视频免费观看|