经典的分治曼哈顿，使用OpenCV加了点可视化，代码美工了属于是
import numpy as np
import cv2
import random
# 输入：有起点和终点的加权网格G
# 输出：G中从起点到终点的一条最长的路线
class Dist:
def __init__(self):
self.left = 0 # 从左侧来需要的代价
self.up = 0 # 从上侧来需要的代价
def Manhattan(D, a, b, ans):
if a == 0 and b == 0:
ans.append([a, b])
return
if D[a][b] == 'up' or b == 0:
Manhattan(D, a - 1, b, ans)
else:
Manhattan(D, a, b - 1, ans)
ans.append([a, b])
if __name__ == "__main__":
while True:
n = random.randint(2, 10)
m = n
img = np.zeros([600, 600, 3])
for i in range(0, n):
for j in range(0, m):
cv2.circle(img, ((j + 1) * 50, (i + 1) * 50), 3, (255, 255, 255), -1)
wight = [[Dist() for _ in range(m)] for _ in range(n)] # 权重矩阵
for i in range(0, n):
for j in range(1, m):
wight[i][j].left = random.randint(1, 10)
for i in range(1, n):
for j in range(0, m):
wight[i][j].up = random.randint(1, 10)
# for i in range(0, n):
# for j in range(0, m):
# print(wight[i][j].left, wight[i][j].up)
for i in range(0, n):
for j in range(1, m):
cv2.putText(img, str(wight[i][j].left), ((j + 1) * 50 - 25, (i + 1) * 50 - 6),
cv2.FONT_HERSHEY_SIMPLEX, 0.5, (0, 255, 0), 1)
for i in range(1, n):
for j in range(0, m):
cv2.putText(img, str(wight[i][j].up), ((j + 1) * 50 + 6, (i + 1) * 50 - 25),
cv2.FONT_HERSHEY_SIMPLEX, 0.5, (255, 0, 0), 1)
cost = [[0] * m for _ in range(n)] # 到达各点所需的代价矩阵
direction = [[''] * m for _ in range(n)] # 到达各点时的方向
for i in range(1, n):
cost[i][0] = cost[i - 1][0] + wight[i][0].up
direction[i][0] = 'up'
cv2.putText(img, str(cost[i][0]), (50 - 8, (i + 1) * 50 - 8),
cv2.FONT_HERSHEY_SIMPLEX, 0.6, (255, 255, 0), 1)
for i in range(1, m):
cost[0][i] = cost[0][i - 1] + wight[0][i].left
direction[i][0] = 'left'
cv2.putText(img, str(cost[0][i]), ((i + 1)*50 - 8,50 - 8),
cv2.FONT_HERSHEY_SIMPLEX, 0.6, (255, 255, 0), 1)
for i in range(1, n):
for j in range(1, m):
if cost[i][j - 1] + wight[i][j].left >= cost[i - 1][j] + wight[i][j].up:
cost[i][j] = cost[i][j - 1] + wight[i][j].left
direction[i][j] = 'left'
else:
cost[i][j] = cost[i - 1][j] + wight[i][j].up
direction[i][j] = 'up'
cv2.putText(img, str(cost[i][j]), ((j + 1) * 50 - 8, (i + 1) * 50 - 8),
cv2.FONT_HERSHEY_SIMPLEX, 0.6, (255, 255, 0), 1)
answer = []
Manhattan(direction, n - 1, m - 1, answer)
print(answer)
cv2.circle(img, (n * 50, m * 50), 3, (0, 0, 255), -1)
for i in range(0, answer.__len__() - 1):
cv2.circle(img, ((answer[i][1] + 1) * 50, (answer[i][0] + 1) * 50), 3, (0, 0, 255), -1)
cv2.line(img, ((answer[i][1] + 1) * 50, (answer[i][0] + 1) * 50),
((answer[i + 1][1] + 1) * 50, (answer[i + 1][0] + 1) * 50), (255, 255, 0), 1)
cv2.putText(img, "MaxLoad: " + str(cost[n - 1][m - 1]), (460, 580),
cv2.FONT_HERSHEY_SIMPLEX, 0.6, (255, 255, 255), 1)
cv2.imshow("Manhattan", img)
key = cv2.waitKey()
if key == 27 or key == 'q' or key == 'Q':
break
