1
zhttty 2014-01-24 16:26:13 +08:00
我真的不是来骗答案然后去面试的……+1
|
2
lentrody 2014-01-24 16:48:15 +08:00
其实就是4X4拼图?
|
4
c742435 2014-01-24 17:05:19 +08:00 1
其实也就C(16,8) = 12870种状态,穷举就完了。
|
5
casparchen 2014-01-24 17:27:48 +08:00
@c742435 问题是问最短的路径。。
|
6
acros 2014-01-24 17:31:12 +08:00
不算智力题吧,算法...
|
7
alexrezit 2014-01-24 17:34:09 +08:00
和这个东西同理吧... 搜一下 tile game algorithm? |
8
gongweixin 2014-01-24 18:18:35 +08:00
@alexrezit 不太一样的, 你的这个每块都是唯一的
|
9
FrankFang128 2014-01-24 18:24:06 +08:00
这不算智力题,已经是算法题的了。
|
10
66beta 2014-01-24 18:28:54 +08:00
算法题,好难
|
11
c742435 2014-01-24 18:34:59 +08:00
@casparchen 好吧 不是12870种,我忽略了光标所在的状态。我写了个示例代码 你可以看看我的思路 不过肯定有错,没跑出来……
@66beta @gongweixin @FrankFang128 求指教 |
12
c742435 2014-01-24 18:35:52 +08:00
package {
import flash.display.Sprite; import flash.text.TextField; public class Untitled extends Sprite { public function Untitled() { var a:Array = new Array; a[0xf00ff] = ""; var counter:int = 0; work(0x00ff, 15, ""); trace(counter); function work(v:uint, p:int, s:String):void { counter += 1; if(0 == counter % 100) { trace(counter); } if(0x5858 == v) { trace("a[" + 0x5858 + "]=" + a[v]); } if(s.length > 600) return; if((p & 3) < 3) { test(1, "U"); } if((p & 3) > 0) { test(-1, "D"); } if(p < 12) { test(4, "L"); } if(p > 3) { test(-4, "R"); } function test(n:int, sadd:String):void { var tempV:uint = calc(n); var tempS:String; var index:int = tempV | ((p + n) << 16); if(!a[index]) { tempS = s + sadd; a[index] = tempS; work(tempV, p + n, tempS); } } function calc(n:int):uint { var fromMask:int = 1 << p;//原有位置被置为目标位置的值 var toMask:int = 1 << (p + n);//目标位置被置为0(光标位置总是为0) return v & (0xffff ^ toMask) & (0xffff ^ fromMask) | ( (v & toMask ) && fromMask); } } } } } |
13
c742435 2014-01-24 18:36:07 +08:00
我擦 格式全乱了,,,,
|
14
alexrezit 2014-01-24 18:37:58 +08:00
@gongweixin
有很大区别么? |
15
txx 2014-01-24 18:47:59 +08:00
BFS 很难么?
|
16
raptium 2014-01-24 19:25:36 +08:00 via iPhone
我也收到这邮件了……
Glow 对吧? |
17
zhufenggood 2014-01-24 19:40:35 +08:00
|
18
felix021 OP |
19
ruoyu0088 2014-01-24 20:21:25 +08:00
就是广度搜索:我的旧电脑也不需要3秒钟。
|
20
ruoyu0088 2014-01-24 20:26:39 +08:00
|
21
ruoyu0088 2014-01-24 20:38:07 +08:00 1
|
22
c742435 2014-01-24 20:47:18 +08:00
a 算出来啦 是DDRRULLDRRRULLDRDLLUURURDDDR
我的之前不小心搞成深搜了 应该是广搜 |
23
c742435 2014-01-24 20:49:36 +08:00
话说怎么贴代码呢?在贴一次乱的吧 不好意思
package { import flash.display.Sprite; import flash.text.TextField; public class Untitled extends Sprite { public function Untitled() { var a:Array = new Array; a[0xf00ff] = ""; var task:Vector.<VPS> = new Vector.<VPS>; task.push(new VPS(0x00ff, 15, "")); var counter:int = 0; while(task.length) { work(); } function work():void { if(!task.length) { return; } var vps:VPS = task.shift(); var v:uint = vps.v, p:int = vps.p, s:String = vps.s; if(0x5a5a == v && 0 == p) { trace("a[" + ((p << 16) | v) + "]=" + s); } if((p & 3) < 3) { test(1, "U"); } if((p & 3) > 0) { test(-1, "D"); } if(p < 12) { test(4, "L"); } if(p > 3) { test(-4, "R"); } function test(n:int, sadd:String):void { var tempV:uint = calc(n); var tempS:String; var index:int = tempV | ((p + n) << 16); if(!a[index]) { tempS = s + sadd; a[index] = tempS; task.push(new VPS(tempV, p+n, tempS)); } } function calc(n:int):uint { var fromMask:int = 1 << p;//原有位置被置为目标位置的值 var toMask:int = 1 << (p + n);//目标位置被置为0(光标位置总是为0) return v & (0xffff ^ toMask) & (0xffff ^ fromMask) | ( (v & toMask ) && fromMask); } } } } } class VPS { var v:uint; var p:int; var s:String; function VPS(v:uint, p:int, s:String) { this.v = v; this.p = p; this.s = s; } } |
24
P233 2014-01-24 20:53:11 +08:00
|
29
chairuosen 2014-01-24 22:34:47 +08:00 2
|
30
chairuosen 2014-01-24 22:40:26 +08:00
@chairuosen 咦? 连接呢 http://jsbin.com/eZUKUPI/1
|
31
P233 2014-01-24 22:43:02 +08:00 1
|
32
P233 2014-01-24 22:45:02 +08:00
@chairuosen 赞
|
33
Muninn 2014-01-24 22:54:33 +08:00
哈哈 赞一下好多人这么花精力去玩的态度
|
34
chairuosen 2014-01-24 23:03:26 +08:00
http://jsbin.com/eZUKUPI/5
又改了改,ESC重置 |
35
ETiV 2014-01-25 00:51:05 +08:00 via iPhone
看上去好像魔方……
我可以毫不费力的把一个完好的魔方拧出乱七八糟的样子 |
36
nan0kai 2014-01-25 08:18:13 +08:00
@chairuosen FF显示畸形
|
37
P233 2014-01-25 08:42:31 +08:00 1
@c742435 又折腾了一下 DDRRULLDRRRULLDRDLLUURURDDDR 好像不对(之前写的有点问题),最后白框在 “右下角” 而不是左上角。
两个版本 去掉了动画,输入指令显示最终结果 http://jsbin.com/ariWinuc/8/ 加了动画效果的按键版本,很不完善,指令不能输入太快,最好也不要出界,不知如何 fix,请大家多指点 http://jsbin.com/ariWinuc/7/ |
38
liushuaikobe 2014-01-25 10:32:19 +08:00
我也收到这封邮件了 +1
|
39
chairuosen 2014-01-25 12:57:07 +08:00 1
@nan0kai box-sizing的原因。。好了 http://jsbin.com/eZUKUPI/11/
|
40
felix021 OP |
41
c742435 2014-01-25 18:08:43 +08:00
|
42
chairuosen 2014-01-25 18:42:57 +08:00
@P233 动画过程加个锁,按键没锁再执行
|
43
sgissb1 2014-01-25 19:13:35 +08:00
类似华容道的算法题,这要怎么推算才能找到规律。。。。
|
44
doskoi 2014-01-28 03:23:27 +08:00
@ruoyu0088 思路是对的,你的电脑只要3秒应该是因为后面的记录都出现过在visited里了,因为你的copy_bit只操作了b2, b1的状态没改变,所以后面的0和1的count都乱了。
|
46
doskoi 2014-01-28 11:58:07 +08:00
@ruoyu0088 我bitwise和python都不算熟悉,请赐教。
你的code,我把target换成了图E的状态,也就是文中RDRDL target_status = (9, int("0011011100010011", 2)) 按照算法应该会返回DRRDL。但是我从return route2和visited.add(status2)的输出来看,不是这样的。 在copy_bit中,我试着重新判断了下b1和b2的值,并且他们一个为0一个不为0的情况下,根据是b1或b2的情况不同,分别把他们设置成0何1,做到模拟移动方块的操作。这样再来运算即可得出图E和图T的状态,分别0.2秒和25分钟。 不对或在不优的地方请指出,谢谢。 |
47
allenhsu 2014-01-28 12:09:33 +08:00
弱弱地飘过,我是这家公司的,当初应聘我用的 bitmap + 一个 currentPos 来描述状态的,大家有兴趣欢迎投简历啊,可以联系我或者直接到官网投简历。
https://www.glowing.com/jobs PS:看来要换题了 |
50
ruoyu0088 2014-01-28 19:40:51 +08:00
@doskoi 所以我的程序中的target_status是两个:
target_status = {(0, int("1010010110100101",2)), (0, int("1010010110100100",2))} 你也应该写两个target_status。 当然修改一下copy_bit,把b1对应的比特设置为0,就不需要两个target了。 |
53
songkaiape 2016-05-23 17:31:30 +08:00
挖坟,楼主这一句我没看懂, visited = set(start_node['state']) ,这里应该意思是用列表存储访问过的状态吧,我觉得应该使用列表, visited=[],visited.append(start_node['state']),但是神奇的是楼主的代码和我改了之后的跑的结果一样。。。而且楼主之前的代码比我改了之后的快很多,不是很懂求解释
|
54
songkaiape 2016-05-23 17:37:16 +08:00
@songkaiape 好吧=。=我发现了。。其实这个 visited 并没有用来当作判断的条件。。。
|
55
songkaiape 2016-05-23 17:38:14 +08:00
@songkaiape 所以按照楼主的意思其实还是应该用 List 才对。不过用了反而性能下降了。。
|
56
songkaiape 2016-05-23 17:44:00 +08:00
@songkaiape 哦不对=。=好像只有第一句是错误的,用 set 的话应该是这样 visited = set(),visited.add(start_node['state']) ,直接 visited = set(start_node['state'])会变成{'0','2','1'}而不是{‘ 2011001100110011 ’},我的 py3 不知道是不是环境一样。不过学到了 SET 的用法,谢谢楼主分享
|