一个类似于八数码的算法题（中兴竞赛题）,该怎么处理

一个类似于八数码的算法题（中兴竞赛题）
一个N*N的矩阵，里面的数字不一定连续（可以重复），但一定能排列成每行、每列之和都相等
在N*N的矩阵下面有两个0，代表两个空格，要求要像拼图游戏一样移动数字，

比如给定3 * 3矩阵

3,1,3
1,2,2
2,4,3
0,0

要求得出目的矩阵（列之和，行之和都为7）

1,3,3
4,1,2
2,3,2
Step:10
7D8L9L6D5R2D1R4U7U10U

后面两行分别是移动的步数和移动的过程，7D表示编号第七的数字（从1开始编号，先行后列）向下移动一次，L是左，R是右，U是向上。

[解决办法]

引用:

引用:

直接bfs就行了，n不是很大的话就用一个int或long long保存状态，前导为0的情况可由数字的长度判断


怎么用int或者int long 保存状态，矩阵中的数字的大小是不确定的比如10*10的矩阵，怎么保存每个数字的位置？

谷歌一下：康托展开，然后你就会了

[解决办法]
没错，N很大是不能用int来表示状态，似乎用数组保存必不可少了， lz现在的问题是如果保存这种状态，显然 N 很大时，不过是启发式搜索还是暴力枚举，lz的计算机是不可能在有限时间解出的。。。。。。。

查看更多 下一篇