久久成人免费日本黄色,欧美成人首页,尤物99国产成人精品视频

EOJ 1148 質(zhì)數(shù)陣

----問(wèn)題描述：

在N*N的棋盤上(1<=N<=10)填入1,2,

N*N共N*N個(gè)數(shù),使得任意兩個(gè)相鄰的數(shù)之和為素?cái)?shù).

例如,當(dāng)N=2時(shí),有

1 2

4 3

----輸入：

每組測(cè)試數(shù)據(jù)一行,為一整數(shù)N(1<=N<=10)

----輸出：

輸出滿足條件的最小序列的方案。

最小序列即將每一行連接起來(lái)組成一行，然后使前面的盡可能小，當(dāng)?shù)谝粋€(gè)數(shù)字相同時(shí)則比較下面一個(gè)，依次類推。

比如當(dāng)Ｎ＝２時(shí)，序列為1 2 4 3，當(dāng)無(wú)滿足條件的方案時(shí)輸出"no answer"。

----樣例輸入：

----樣例輸出：

1 2

4 3

----分析：

深度優(yōu)先搜索，

從上往下，從左往右，依次確定每個(gè)位置的數(shù)字，

確定某個(gè)位置的數(shù)字時(shí)，從小到大嘗試所有可用數(shù)字，

優(yōu)化方法，見代碼注釋。

/**********************************************************

版本五：

保存計(jì)算結(jié)果為字符串。

#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;

// 當(dāng) 1 == n2 時(shí)，headEven 不會(huì)被使用

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;

}

// 左上角必然為數(shù)字 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;

}

/**********************************************************

版本四：

保存計(jì)算結(jié)果，避免重復(fù)計(jì)算。

#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;

// 當(dāng) 1 == n2 時(shí)，headEven 不會(huì)被使用

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;

}

// 左上角必然為數(shù)字 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; // 對(duì)無(wú)解的情況，未保存，會(huì)重復(fù)計(jì)算

}

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 （對(duì) 9 == n 時(shí)太慢）

備選鏈分奇偶。

#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;

// 當(dāng) 1 == n2 時(shí)，headEven 不會(huì)被使用

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;

}

// 左上角必然為數(shù)字 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

加入備選鏈優(yōu)化。

#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 閱讀(613) 評(píng)論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè)

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 微軟2014實(shí)習(xí)生及秋令營(yíng)技術(shù)類職位在線測(cè)試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊(cè)

ACM

AI

LaTeX

安全

編程語(yǔ)言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問(wèn)題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

EOJ 1148 質(zhì)數(shù)陣