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

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)


----輸出:

輸出滿足條件的最小序列的方案。
最小序列即將每一行連接起來組成一行,然后使前面的盡可能小,當第一個數字相同時則比較下面一個,依次類推。
比如當N=2時,序列為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, 
0xffsizeof(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(00) ) {
                
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)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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在线| 亚洲免费黄色| 免费亚洲一区| 黄色在线成人| 亚洲一区在线免费观看| 六月婷婷久久| 欧美日韩免费高清一区色橹橹| 国产午夜精品福利|