Submission by @__dAi00

from itertools import combinations
wh = input()
w, h = list(map(int, wh.split(" ")))
m = []

for i in range(h):
    line = input()
    items = list(map(int, line.split(" ")))
    m.append(items)

def cost(path):
    y, x = 0, 0
    c = m[y][x]
    for p in path:
        if p == 'E': x += 1
        elif p == 'S': y += 1
        elif p == 'W': x -= 1
        elif p == 'N': y -= 1
        else: raise
        c += m[y][x]
    return c

minc = -1
minp = ""
for i in combinations(range((w-1)*2), w-1):
    path = ["E" for _ in range((w-1) * 2)]
    for _i in i:
        path[_i] = "S"
    c = abs(cost(path))
    if minc == -1 or minc > c:
        minc = c
        minp = path
print("".join(minp))

Battle History