ACM题(#2634 Collecting Stones)

lugionline

注意每个行，列，可能出现不同的形状，价值的记录

〇〇

原帖由 lugionline 于 2011-4-12 11:18 发表
1. 不要保留路径，只需要保留一个形状就可以了(64bit，每个bit表示是否访问过)
2. 搜索1-4列，得到从开始点出发到达第四列每个位置的记录
3. 搜索8-5列（反向)，得到从结束点到达第5列每个位置的记录
4. 每个位置的记录可以这样表示 行，列，形状，价值
5. 匹配2和3搜索的结果

我就是2345实现的，但效率还差很远

lugionline

[0, 0]        Count = 1       
[0, 1]        Count = 1       
[0, 2]        Count = 1       
[0, 3]        Count = 1       
[0, 4]        Count = 1       
[0, 5]        Count = 1       
[0, 6]        Count = 1       
[0, 7]        Count = 1       
[1, 0]        Count = 15       
[1, 1]        Count = 15       
[1, 2]        Count = 15       
[1, 3]        Count = 15       
[1, 4]        Count = 15       
[1, 5]        Count = 15       
[1, 6]        Count = 15       
[1, 7]        Count = 15       
[2, 0]        Count = 218       
[2, 1]        Count = 218       
[2, 2]        Count = 218       
[2, 3]        Count = 218       
[2, 4]        Count = 218       
[2, 5]        Count = 218       
[2, 6]        Count = 218       
[2, 7]        Count = 218       
[3, 0]        Count = 3165
[3, 1]        Count = 3165
[3, 2]        Count = 3165
[3, 3]        Count = 3165
[3, 4]        Count = 3165
[3, 5]        Count = 3165
[3, 6]        Count = 3165
[3, 7]        Count = 3165

大致计算了下，后面count是形状的数量，总数大概在3万左右，应当不会很慢吧，没用SQL写

lugionline

2，3这个过程是很快的，基本上毫秒数量级(C#)

至于后面的匹配，我觉得可以用开一个bit数组（数量不超过2000001），然后循环8次处理第四列每行的数据，应当很快就能完成

〇〇

[0，0]是c语言的数组？

lugionline

当然SQL的做法可以把两个结果集链接起来找需要价值的记录，然后查行的差异+1， 0 -1的记录可能慢点，但慢不到哪里去吧？ 才3万×3万啊。

〇〇

貌似30毫秒440K也算不出来

lugionline

是坐标位置，表示从0，0开始到达这个点的记录数
貌似我少算了几种

第一列只有1种，第二列好像有22种 (6 * 3 + 2 * 2), 大致估计是 8 * 3

第三例差不多应当 8 * 3 * 8 * 3 = 576，第四列 576 * 24 = 13824

这样总共大概10万条记录的样子

lugionline

原帖由 〇〇 于 2011-4-12 12:14 发表
貌似30毫秒440K也算不出来

人家是 C啊，谁让你用SQL去比的啊

lugionline

不可思议，发现程序中少写了一个方向，这下该对了

[0, 0]        Count = 1       
[0, 1]        Count = 1       
[0, 2]        Count = 1       
[0, 3]        Count = 1       
[0, 4]        Count = 1       
[0, 5]        Count = 1       
[0, 6]        Count = 1       
[0, 7]        Count = 1       
[1, 0]        Count = 22       
[1, 1]        Count = 22       
[1, 2]        Count = 22       
[1, 3]        Count = 22       
[1, 4]        Count = 22       
[1, 5]        Count = 22       
[1, 6]        Count = 22       
[1, 7]        Count = 22       
[2, 0]        Count = 450       
[2, 1]        Count = 450       
[2, 2]        Count = 450       
[2, 3]        Count = 450       
[2, 4]        Count = 450       
[2, 5]        Count = 450       
[2, 6]        Count = 450       
[2, 7]        Count = 450       
[3, 0]        Count = 9174
[3, 1]        Count = 9174
[3, 2]        Count = 9174
[3, 3]        Count = 9174
[3, 4]        Count = 9174
[3, 5]        Count = 9174
[3, 6]        Count = 9174
[3, 7]        Count = 9174