首先,无所谓哪里密集哪里不密集的说法,这是人为的区分,需要首先遍历全部格子才能确定,是最慢的算法,全部遍历过了就可以得出最优的路线了.
既然用贪心算法,为了思考方便,可以假设棋盘无穷大,算法的目的是判断下一步该往右走还是往下走,思想如下:
判断当前格子右、下两个相邻的格子是否有金块,情形如下：
1）如果一个有一个没有,则往有金块的格子走
2）如果都没有或都有,则需要判断往哪个方向走能更快的拾到下一个金块,方法如下：
让机器人假设地各往两个方向走一步,然后对当前格子作判断情形如下：
A)一个格子继续走能拾到金块,另一个不能,则上一步往该格子走
B)如果仍旧都有或都没有,重复2）直到找到符合A）的情形.
假设棋盘是N*N个格子,则贪心算法最坏的情形是要遍历整个棋盘,比如只有第一个格子有金块时,就需要遍历整个棋盘才能确定走法.最好的情形也需要遍历4*N个格子.
时间复杂度上来算的话,应该是O（nLogn）