久久天天躁狠狠躁夜夜av浪潮 ,久久久艹,久久影视国产亚洲

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"。

----樣例輸入：

----樣例輸出：

1 2

4 3

----分析：

深度優先搜索，

從上往下，從左往右，依次確定每個位置的數字，

確定某個位置的數字時，從小到大嘗試所有可用數字，

優化方法，見代碼注釋。

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

版本五：

保存計算結果為字符串。

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

}

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

版本四：

保存計算結果，避免重復計算。

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

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1148 質數陣