我正在尝试解决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 ddef 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 hereif __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
谢谢！
回答：
明白了
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 ddef 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 hereif __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)