清扫房间全面攻略，发一桶貌似被和谐了

Sarisoul

永远的呱哥哥 发表于 2017-3-31 15:40
Dijstra对于这个问题并没有什么帮助啊，所有路线的权重都一样也不需要求最短路径，应该是salesman问题，不 ...

对的Dijkstra不可行，我一开始想用Dijkstra是感觉可以将每条直线上的格子数表示为权重，但是想了一分钟后发现这问题根本不是最短路径问题，因为你无论如何遍历你的路径长度永远等于25-障碍数，所以放弃了

然后拓扑排序的话有点interesting，我比较初步的想法是将每个转折点作为node分别用记录它们的入度和neighbor？就是neighbor数组求起来可能有点麻烦，一个点它对应的各个方向所有的临界点都是他的neighbor，不过，值得一试，就是时间复杂度可能还会是O（n^2）

动态规划是我码好dfs之后就想做的，但是有三个方面：一动态规划在2d网格上的时间复杂度很难优于n^2；二是动态规划只能告诉你从某点出发到某点是否可行，不能记录中间的决策，即转折点的坐标；三是楼主真的想不到状态转移方程会是哪样…… 我觉得光凭这几点还不足以ban掉动态规划，毕竟我一直没学好。。。

salesman我还真没想过，回头看看！！！

然后其实从时间复杂度角度分析的话，比o（n^2）优的无非两种，要么线性时间复杂度，这个绝对不可能，你肯定是要检查每个点的可能性，检查这个点的时间不可能为O（1）。那么另外一种就是O（nlogn）了。log(n)的话我只想到了binary search，但是这个问题完全看不出来和二分法有什么关系。。

我怀疑这题的最优时间复杂度就是O（n^2），明天去请教一下大神。。。

Sarisoul

当场我就吓尿了 发表于 2017-4-1 10:18
试了下，只在右边出现了
File "/temp/file.py", line 89
    cl = clean(points)

检查一下上一行points 的中括号， 格式应该为points = [[x,y],[x,y],[x,y]]     你应该在改坐标的时候落了一个括号

Sarisoul

淸眸乄泠顏 发表于 2017-4-1 10:53
Error response from daemon: Container bae4a2dfd635ed1e36e07ce26e0dbc73b52ea59ad3dcc868d0a5df10779b58 ...

Time out 的话可以刷新一下重新run，这个程序最多跑2到3秒钟，如果等了很久都没反应的话就是网络问题了

Sarisoul

丶夏末微凉 发表于 2017-4-1 13:17
Error response from daemon: Container 53a445a418d97207136c4f3406e1031e7a4a09cc4242f1097f2e62b668f234 ...

超时了，刷新一下，重新run，这个网站今天响应有点慢。。

Sarisoul

小小虫虫虫 发表于 2017-4-2 01:06
这个遍历问题其实除了穷举我还真想不到其他解法，点之间不存在可以数学描述的关系，所以我只能做一个二维结 ...

对的，已经确认过了只能做到n平方时间复杂度

Sarisoul

魔人兔啾啾 发表于 2017-4-2 12:08
大神。。今天变成6个或者7个障碍物了

障碍多了，在points数组里多加一个坐标即可，[x,y]

Sarisoul

白神经丶勿爱 发表于 2017-4-3 01:26
一直这样

File "/temp/file.py", line 3

你查一下你第三行class前面是不是多了一个3，可能复制的时候把行号也复制进去了，建议直接用论坛我贴的代码的最后一行点击复制。