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)
    exit()

if w < 30: # not large
    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))
    exit()

from copy import deepcopy
mm = deepcopy(m)
m = []
ppp = ""
for s,t in [(0,11), (10,11), (20, 10)]:
    w = t
    h = t
    for i in range(s, s+t):
        _m = []
        for j in range(s, s+t):
            _m.append(mm[i][j])
        m.append(_m)

    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
    ppp += "".join(minp)
print(ppp)

Battle History