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 阅读(572) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithm课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理