当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2479幻方3阶4阶
255+

题目大意:给定N*N个数,把它们填入N*N的方格中,使每行每列和两个对角线里数的和都相等。数据保证有可行解,输出任一解即可。

输入

第一行一个整数N。
第二行N*N个整数,表示要填入幻方中的数。

输出

N行,每行N个整数,代表填好的幻方

样例输入

3 1 2 3 4 5 6 7 8 9

样例输出

2 7 6 9 5 1 4 3 8

提示

数据点 特征
1 N=3
2
3
4 N=4且数字种类数不超过9
5
6 4

4815960 32237520 2073804 -668352 -22605600 -668352 15784584 4815960 10300272 -6152664 10300272 15784584 -6152664 7558116 2073804 7558116

7 4

-80196146 -51775286 -34722770 -29038598 -17670254 -11986082 -6301910 -617738 10750606 16434778 22118950 27803122 39171466 44855638 61908154 90329014

8 N = 4
9
10

对于所有数据点,填入数字的绝对值不超过10^9。

解题思路

格子搜索,一个一个格子填入数字,每次从n*n个数字里面选一个没填过的。对应n=3,即使不剪枝,时间复杂度也不超过10!,但对于n=4,必定超时。

首先考虑剪枝,没有最优,只有可不可行,那就进行可行性剪枝。什么是可行呢?要求每行每列每斜都相等,这个值是可以算出来的,即m=n*n个数的和除以n。在填完一行、一列、一斜,就判断那n个数是否等于m,如果不相等,就不需要搜索了。结果还是超时!

再想想,搜索顺序对速度有没有影响呢?终于找到规律,如果n=4,从上到下、从左到右的格子依次是0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,那么我们可以按照这样的顺序进行搜索:0,1,2,3,4,5,6,7,8,12,9,13,10,11,14,15,这样的话,3、7、12、9、13、11、14、15都是可以直接确定的,也就是说只有8个数需要枚举,复杂度是16*15*14*12*11*10*8*4,即从16个数里面选8个数的复杂度(还跟顺序有关)

接下来就是慢慢考虑到哪个格子的时候,需要判断些什么,如3判断第一行、7判断第二行、12判断第一列、9判断撇、13判断第二列、11判断第三行、14判断第三列、15判断第四行第四列以及捺。

程序实现

更多
SSOJ2479幻方3阶4阶:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter