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;
char output[MAXSIZE+1];
char str[5]="NESW";
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(){
    std::random_device rnd; 
    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;
    int N=h1+w1;
/*    rep(i,h1){
        printf("S");
    }
    rep(j,w1){
        printf("E");
    }
    printf("\n");*/    
      // 昇順にソート済みの入力
    
//    int v[100]={0} ;
    vector <int> v (N);
    rep(i,h1){
        v[i]=2;//S
    }
    rep(j,w1){
        v[h1+j]=1;//E
    }
    /*rep(i,N){
        printf("%d ",v[i]);
    }*/
    int globalbest =10000000;
    for (int i=0;i<1;i++){
        int score=search(v,N);
        if (score<0)score*=-1;
        if (score<globalbest){
            globalbest=score;
            for (int i=0;i<N;i++){
                output[i]=str[v[i]];
            }
        }
        next_permutation(v.begin(), v.end());
    } 
  //  printf("%d \n",globalbest);
    for (int i=0;i<N;i++){
        printf("%c",output[i]);
    }
    printf ("\n");

    return 0;
}

Battle History