python - 优化扫地机器人的路径

Question

我正在尝试解决 Hackerrank 上的 Botclean 问题: https://www.hackerrank.com/challenges/botclean

我想出的解决方案是用最短距离扫描电路板，寻找脏瓷砖，然后导航到它，清洁它，然后重复直到全部干净。

代码:

nextD = []

def next_move(posr, posc, board):
    global nextD

    if nextD == []:
        nextD = next_d(posr,posc,board)


    if (nextD[0] == posr) and (nextD[1] == posc):
        print("CLEAN")
        board[posr][posc] = "-"
        nextD = []
        return 

    if posc < nextD[1]:
        print("RIGHT")
        return
        #posc += 1
    elif posc > nextD[1]:
        print("LEFT")
        return
        #posc -= 1 

    if posr < nextD[0]:
        print("DOWN")
        return
        #posr += 1
    elif posr > nextD[0]:
        print("UP")
        return
        #posr -= 1


#find closest d
def next_d(posr, posc, board):
    arr = []
    for i in range(len(board)):
        try:
            #print("Distance to: ", i, board[i].index('d'), abs(i-posc) + abs(board[i].index('d')))
            vals = [abs(i-posr) + abs(board[i].index('d')-posc), i, board[i].index('d')]
            arr.append(vals)
        except ValueError:
            pass

    arr.sort()
    return [arr[0][1], arr[0][2]]

# Tail starts here
if __name__ == "__main__":
    pos = [int(i) for i in input().strip().split()]
    board = [[j for j in input().strip()] for i in range(5)]
    next_move(pos[0], pos[1], board)

我卡在 17.60/17.82。我的机器人在测试用例上得到 16、20、34、26。最好的分数是 16、25、28 和 18。讨论说要实现一个贪心算法，但我不完全确定在这种情况下如何实现。有什么优化这个问题的建议吗？我是不是完全错了？

编辑:时间不是标准。所以反复扫描板子不一定有问题。

如果您想观看它的实际效果: https://www.hackerrank.com/showgame/4843664

谢谢!

Answer 1

知道了

nextD = []
def next_move(posr, posc, board):
    global nextD

    if nextD == []:
        nextD = next_d(posr,posc,board)

    if (nextD[0] == posr) and (nextD[1] == posc):
        print("CLEAN")
        board[posr][posc] = "-"
        nextD = []
    elif posc < nextD[1]:
        print("RIGHT")
    elif posc > nextD[1]:
        print("LEFT")
    elif posr < nextD[0]:
        print("DOWN")
    elif posr > nextD[0]:
        print("UP")


#find closest d
def next_d(posr, posc, board):
    val = len(board) * 2
    nextD = []
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] == 'd' and abs(i - posr) + abs(j - posc) < val:
                val = abs(i - posr) + abs(j - posc)
                nextD = [i, j]

    return nextD


# Tail starts here
if __name__ == "__main__":
    pos = [int(i) for i in input().strip().split()]
    board = [[j for j in input().strip()] for i in range(5)]
    next_move(pos[0], pos[1], board)