NOIP1997数字方阵

2013年12月5日1,4312

题目描述

在N*N的棋盘上(1<N≤10)填入1,2,…N*N共N*N个数,使得任意两个相邻的数之和为素数.例如,当N=2时,有 :
1
2
4
3
其相邻数的和为素数的有:1+2,1+4,4+3,2+3。
当N=4时,一种可以填写的方案如下:
1
2
11
12
16
15
8
5
13
4
9
14
6
7
10
3

在这里我们约定:左上角的格子里必须放数字1。

输入

一个正整数N。

输出

若有多种解,则需输出第一行之和最小,若第一行和相同,则输出第一列之和最小的排列方案;若无解,则输出”No solution”。若有解,第一行为空格分割的两个正整数,分别是该排列方案的第一行、第一列各数字之和。以下n行输出该排列方案,每个数字占4个字符,不足4位的在数字前用空格补齐。

样例输入

2

样例输出

3 5 1 2 4 3

代码

最傻逼的回溯,显然超时

改进一下素数判断和增加剪枝160ms

 

 

  • 吴桐2014年5月21日 下午6:11 回复

    学长解释一下啊,现在的程序就是过不了。

    #1  
    • hzwer2014年5月21日 下午7:56 回复
      admin

      忘了。。

      #11