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

def dfs(c, x, y, visited, p):
    c += m[y][x]
    if x == w-1 and y == h-1:
        return abs(c), p
    minc = -1
    minp = ""
    for xx,yy,pp in [(x-1, y, "W"), (x+1, y, "E"), (x, y-1, "N"), (x, y+1, "S")]:
        if xx >= 0 and xx < w and yy >= 0 and yy < h and not visited[yy*w+xx]:
            visited[yy*w + xx] = True
            cc, pp = dfs(c, xx, yy, visited, p+pp)
            visited[yy*w + xx] = False
            if not cc == -1: # valid path
                if minc == -1 or minc > cc:
                    minc = cc
                    minp = pp
    return minc, minp



if w == 3 or w == 5: #tiny
    v = [True] + [False for _ in range(w*h-1)]
    cc, pp = dfs(0, 0, 0, v, "")
    print(pp)
    print(cc)
    exit()

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