cc 2012 02 smvsevil

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
typedef unsigned long long LL;
#define FOR(k,a,b) for(LL k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(b-1); k >= (a); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))
#ifdef HOME
#include "debug.h"
#else
#define debug()
#endif

class MAZE
{
    int mHeight;
    int mWidth;
    vector<vector<bool> > mMaze;
    int mActX;
    int mActY;
    int mEndX;
    int mEndY;
    vector<vector<int> > mDistToEnd;
    vector<vector<string> > mPath;
public:
    MAZE(vector<vector<bool> >& maze, int startx, int starty, int endx, int endy):
      mActX(startx+1),
          mActY(starty+1),
          mEndX(endx+1),
          mEndY(endy+1)
      {
          mMaze.swap(maze);
          mHeight=mMaze.size();
          mWidth=mMaze[0].size();
          //calculate dist to end
          mDistToEnd.resize(mHeight,vector<int> (mWidth, 10000));
          mPath.resize(mHeight,vector<string> (mWidth));
          mDistToEnd[mEndY][mEndX]=0;
          bool improve=true;
          while(improve)
          {
              improve=false;
              REP(i,mWidth)
                  REP(j,mHeight)
                  if(mMaze[j][i])
                  {
                      if(mDistToEnd[j][i-1]+1<mDistToEnd[j][i])
                      {
                          mDistToEnd[j][i]=mDistToEnd[j][i-1]+1;
                          mPath[j][i]=mPath[j][i-1]+'W';
                          improve=true;
                      }
                      if(mDistToEnd[j][i+1]+1<mDistToEnd[j][i])
                      {
                          mDistToEnd[j][i]=mDistToEnd[j][i+1]+1;
                          mPath[j][i]=mPath[j][i+1]+'E';
                          improve=true;
                      }
                      if(mDistToEnd[j-1][i]+1<mDistToEnd[j][i])
                      {
                          mDistToEnd[j][i]=mDistToEnd[j-1][i]+1;
                          mPath[j][i]=mPath[j-1][i]+'N';
                          improve=true;
                      }
                      if(mDistToEnd[j+1][i]+1<mDistToEnd[j][i])
                      {
                          mDistToEnd[j][i]=mDistToEnd[j+1][i]+1;
                          mPath[j][i]=mPath[j+1][i]+'S';
                          improve=true;
                      }
                  }
          }
          REP(i,mWidth)
              REP(j,mHeight)
              reverse(mPath[j][i].begin(),mPath[j][i].end());
      }
      int GetActDist()
      {
          return mDistToEnd[mActY][mActX];
      }
      const string& GetPath()
      {
          return mPath[mActY][mActX];
      }
      void Step(const string& s)
      {
          REP(i,s.size())
          {
              switch(s[i])
              {
              case 'W':
                  if(mMaze[mActY][mActX-1])
                      --mActX;
                  break;
              case 'E':
                  if(mMaze[mActY][mActX+1])
                      ++mActX;
                  break;
              case 'N':
                  if(mMaze[mActY-1][mActX])
                      --mActY;
                  break;
              case 'S':
                  if(mMaze[mActY+1][mActX])
                      ++mActY;
                  break;
              default:
                  assert(false);
              }
          }
      }
      int StepCalc(const string& s) const
      {
          int x=mActX,y=mActY;
          REP(i,s.size())
          {
              switch(s[i])
              {
              case 'W':
                  if(mMaze[y][x-1])
                      --x;
                  break;
              case 'E':
                  if(mMaze[y][x+1])
                      ++x;
                  break;
              case 'N':
                  if(mMaze[y-1][x])
                      --y;
                  break;
              case 'S':
                  if(mMaze[y+1][x])
                      ++y;
                  break;
              default:
                  assert(false);
              }
          }
          return mDistToEnd[y][x];
      }
};

int main()
{
#ifdef HOME
    clock_t start=clock();
    freopen ("in.txt","r",stdin);
    freopen ("out.txt","w",stdout);
    freopen ("out_err.txt","w",stderr);
#endif
    std::ios_base::sync_with_stdio (false);
    int T,K,M,N;
    cin >> T;
    REP(testcase,T)
    {
        cin >> K;
        string s;
        vector<MAZE> v;
        REP(ttt,K)
        {
            cin >> M >> N;
            int sx, sy, ex, ey;
            vector<vector<bool> > maze(M+2,vector<bool> (N+2,false));
            REP(i,M)
            {
                cin >> s;
                REP(j,N)
                {
                    switch(s[j])
                    {
                    case 'S':
                        maze[i+1][j+1]=true;
                        sx=j,sy=i;
                        break;
                    case 'E':
                        maze[i+1][j+1]=true;
                        ex=j,ey=i;
                        break;
                    case '.':
                        maze[i+1][j+1]=true;
                        break;
                    }
                }
            }
            v.push_back(MAZE(maze,sx,sy,ex,ey));
        }
        vector<bool> used(K);
        string out;
        REP(round,K)
        {

            int best=-1,bestscore=100000;;
            REP(i,K)
                if(!used[i])
                {
                    best=i;
                    break;
                }
                REP(i,K)
                {
                    if(!used[i])
                    {
                        int scorei=v[i].GetActDist();
                        const string& acts=v[i].GetPath();
                        REP(j,K)
                            if(!used[j] && j!=i && scorei+v[j].StepCalc(acts)<bestscore)
                            {
                                best=i;
                                bestscore=scorei+v[j].StepCalc(acts);
                            }
                    }
                }
                assert(!used[best]);
                const string& acts=v[best].GetPath();
                REP(i,K)
                    if(!used[i])
                        v[i].Step(acts);
                out+=acts;
                used[best]=true;
        }
        cout << out << endl;
    }
#ifdef HOME
    fprintf(stderr,"time=%.3lfsec\n",0.001*(clock()-start));
#endif
    return 0;
}