def solve(H, W, AS): from collections import defaultdict edges = defaultdict(dict) for x in range(W): for y in range(H): pos = y * W + x if x < W - 1: edges[pos + 1][pos] = AS[y][x] if x > 0: edges[pos - 1][pos] = AS[y][x] if y < H - 1: edges[pos + W][pos] = AS[y][x] if y > 0: edges[pos - W][pos] = AS[y][x] d1 = one_to_all(W - 1, H * W, edges) d2 = one_to_all(W * (H - 1), H * W, edges) d3 = one_to_all(W * H - 1, H * W, edges) INF = 9223372036854775807 ret = INF for x in range(W): for y in range(H): pos = y * W + x v = d1[pos] + d2[pos] + d3[pos] - 2 * AS[y][x] if v < ret: ret = v return ret