Submission by @lip_of_cygnus

#define H 50
#define W 50
#define MAXSIZE 100
#include <random>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) ((x).begin(),(x).end())
using ll = long long;
typedef long long ll;
typedef long long int64;
typedef long long lint;
typedef long long lli;
int gridlist[H][W];
int flg[H][W];
int v[MAXSIZE];
using namespace std;
random_device rnd; 
char output[MAXSIZE+1];
char str[5]="NESW";
void shuffle(vector <int> array, int size) {
    for(int i = 0; i < size; i++) {
        int j = rnd()%size;
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    /*for(int i = 0; i < size; i++) {
        printf("%d ",array[i]);
    }
    printf("\n");*/
}
int search(vector <int> v,int N){
    int score =gridlist[0][0];
    int posx=0,posy=0;
    for (int i=0;i<N;i++){
        switch (v[i]){
            case 0:
            posy-=1;
            break;
            case 1:
            posx+=1;
            break;
            case 2:
            posy+=1;
            break;
            case 3:
            posx-=1;
            break;
        }
    //    printf("%d %d %d %d\n",posx,posy,gridlist[posx][posy],score);
        score+=gridlist[posx][posy];
    }
    return score;
}
int main(){
    int h,w;
    scanf("%d %d",&h,&w);
    
    rep(j,h)
    {
        rep(i,w){
           scanf("%d ",&gridlist[j][i]);
        }
    }
    rep(j,h){
        rep(i,w){
        //    printf("%d ",gridlist[j][i]);            
        }
      //  printf("\n");
    }
    int h1=h-1;
    int w1=w-1;
/*    rep(i,h1){
        printf("S");
    }
    rep(j,w1){
        printf("E");
    }
    printf("\n");*/    
      // 昇順にソート済みの入力
    
//    int v[100]={0} ;
    /*rep(i,N){
        printf("%d ",v[i]);
    }*/
    int OPTION=0;
    int sabunh1;
    int sabunw1;
    if (OPTION){
        int tmph1=h1,tmpw1=w1;
        if (h1>10){
            h1=10;
        }
        if (w1>10){
            w1=10;
        }
        sabunh1=tmph1-h1;
        sabunw1=tmpw1-w1;
    }
    int N=h1+w1;
    vector <int> v (N);
    rep(i,h1){
        v[i]=2;//S
    }
    rep(j,w1){
        v[h1+j]=1;//E
    }

    int globalbest =10000000;
    int step=100000000/(h1+w1);
    for (int i=0;i<step;i++){
        int score=search(v,N);
        if (score<0)score*=-1;
       // printf("%d\n",score);
        if (score<globalbest){
            globalbest=score;
            for (int i=0;i<N;i++){
                output[i]=str[v[i]];
            }
        }
        shuffle(v,N);
        //next_permutation(v.begin(), v.end());
    }

  //  printf("%d \n",globalbest);
    if(OPTION){
        for (int i=0;i<sabunh1;i++){
            printf("S");
        }
        for (int i=0;i<sabunw1;i++){
            printf("E");
        }
        for (int i=0;i<N;i++){
            printf("%c",output[i]);
        }
        printf ("\n");

    } else{
    for (int i=0;i<N;i++){
        printf("%c",output[i]);
    }
    printf ("\n");

    }

    return 0;
}

Battle History