/*
setter solution
Split the warehouse into 5 regions:
x333333
1322222
1455555
1455555
1455555
1455555
1455555
Ideally, fill in the regions as follows:
1: earliest to drop off shipments
2: next earliest to drop off shipments
3: last to pick up shipments
4: next last to pick up shipments
5: everything else
It's not possible to follow them exactly if there are shipments that are picked
up late and dropped off early, which will be special-cased as needed.
Single-character instructions are used, then expanded at the end. Lower case
characters are used in place of load and unload instructions. For example,
"w" is used instead of "LW" or "UW". It is unambiguous because at most one
interpretation is ever valid. See "Expand" function.
*/
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
char Transform(const char* before, const char* after, char c)
{
const char* pos = strchr(before, c);
if (!pos)
return c;
return after[pos-before];
}
// Instruction that does the opposite of the given instruction
char Opposite(char c)
{
static const char* before = "NWSEPDnwse";
static const char* after = "SENWDPnwse";
return Transform(before, after, c);
}
// Find a set of instructions that undo the effects of another set of instructions
std::string Undo(std::string s)
{
std::transform(s.begin(), s.end(), s.begin(), Opposite);
std::reverse(s.begin(), s.end());
return s;
}
// Remove adjacent moves that cancel eachother out, such as a "N" followed by a "S"
std::string Annihilate(std::string s)
{
std::string res;
for (size_t i = 0; i < s.size(); i++)
{
if (!res.empty() && res.back() == Opposite(s[i]))
res.pop_back();
else
res.push_back(s[i]);
}
return res;
}
// Expand a compact instruction sequence into the format required by the judge
std::string Expand(std::string s)
{
std::string res;
bool has = false;
for (size_t i = 0; i < s.size(); i++)
{
if (std::islower(s[i]))
{
res.push_back(has ? 'U' : 'L');
res.push_back(toupper(s[i]));
has = !has;
}
else
{
res.push_back(s[i]);
if (s[i] == 'P' || s[i] == 'D')
has = !has;
}
}
return res;
}
// Reflect direction across diagonal line
char Transposed(char c)
{
return Transform("NWSE", "WNES", c);
}
// Transform a (expanded) solution with C rows and R columns into one with R rows and C columns
std::string Transpose(std::string s)
{
std::transform(s.begin(), s.end(), s.begin(), Transposed);
return s;
}
// Assuming the forklift starts at the entrance, find the first shipment it picks up
std::pair<int, int> FirstShipment(std::string route)
{
int r = 0, c = 0;
for (char i : route)
{
switch (toupper(i))
{
case 'N': r--; break;
case 'S': r++; break;
case 'W': c--; break;
case 'E': c++; break;
}
if (islower(i))
break;
}
return std::make_pair(r, c);
}
// Extract all shipments from the warehouse, in order from 0 to R*C-2
std::string Solve(const int R, const int C, int warehouse[20][20], int phase)
{
std::string res;
int len = R*C-1;
int row[400], col[400];
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
{
if (r == 0 && c == 0)
continue;
row[warehouse[r][c]] = r;
col[warehouse[r][c]] = c;
}
for (int s = 0; s < len; s++)
{
while (true)
{
// Try a bfs first
char mark[20][20] = {{}};
std::pair<int, int> q[400];
int qfront = 0, qback = 1;
q[0].first = row[s];
q[0].second = col[s];
static const int dr[4] = {-1, 0, 1, 0};
static const int dc[4] = { 0,-1, 0, 1};
const char dd[4] = {'N','W','S','E'};
while (qfront != qback && !mark[0][0])
{
int r = q[qfront].first;
int c = q[qfront].second;
qfront++;
for (int d = 0; d < 4; d++)
{
int nr = r-dr[d];
int nc = c-dc[d];
if (!(0 <= nr && nr < R && 0 <= nc && nc < C))
continue;
if (mark[nr][nc] || warehouse[nr][nc] != -1)
continue;
mark[nr][nc] = d+1;
q[qback].first = nr;
q[qback].second = nc;
qback++;
}
}
// Found a path
if (mark[0][0])
{
std::string route;
int r = 0;
int c = 0;
while (r != row[s] || c != col[s])
{
int d = mark[r][c]-1;
route.push_back(dd[d]);
r += dr[d];
c += dc[d];
}
// Ignore paths that waste too many moves
int wastedMoves = route.length() - row[s] - col[s];
if (wastedMoves == 0 || ((row[s] == 0 || col[s] == 0) && wastedMoves == 2))
{
// Drop it off
char loadDir = tolower(route.back());
route.pop_back();
res.append(route);
res.push_back(loadDir);
res.append(Undo(route));
res.push_back('D');
warehouse[row[s]][col[s]] = -1;
break;
}
}
// Going to need to move something out of the way before trying again.
std::string route;
// A bit of trial and error was needed to get all this right
if (phase == 0)
{
assert(col[s] == 0);
assert(warehouse[0][2] == -1);
route.push_back('E');
route.append(row[s]-1, 'S');
route.push_back('s');
if (warehouse[1][0] == -1)
{
route.append(row[s]-2, 'N');
route.append("wNW");
}
else
{
route.append(row[s]-1, 'N');
route.append("eW");
}
}
else
{
if (row[s] == 0 && col[s] == 2 && warehouse[1][1] == -1)
route = "eEsW";
else if (col[s] == 1)
{
if (warehouse[1][0] != -1)
route = "se";
else
route = "SseN";
}
else if (row[s] == 0)
{
if (warehouse[1][1] == -1)
{
route.push_back('S');
route.append(col[s]-1, 'E');
route.push_back('e');
if (warehouse[0][1] == -1)
{
route.append(col[s]-2, 'W');
route.append("nWN");
}
else
{
route.append(col[s]-1, 'W');
route.append("sN");
}
}
else if (warehouse[0][1] == -1 && warehouse[0][2] == -1)
{
route = "EES";
route.append(col[s]-3, 'E');
route.push_back('e');
route.append(col[s]-3, 'W');
route.append("NWWs");
}
else
route = "SesN";
}
else if (col[s] == 0)
route = "SseN";
else
route = "SesN";
}
res.append(route);
std::pair<int, int> before = FirstShipment(route);
std::pair<int, int> after = FirstShipment(Undo(route));
assert(warehouse[before.first][before.second] != -1);
assert(warehouse[after.first][after.second] == -1);
std::swap(warehouse[before.first][before.second], warehouse[after.first][after.second]);
row[warehouse[after.first][after.second]] = after.first;
col[warehouse[after.first][after.second]] = after.second;
}
}
// remove extraneous moves
return Annihilate(res);
}
// GetRoute helper - get last unmarked shipment by arrival order
inline int GetLastUnmarked(bool mark[], const int ord[], int& rpos)
{
while (mark[ord[rpos]])
rpos--;
mark[ord[rpos]] = true;
return ord[rpos];
}
// GetRoute helper - get first unmarked shipment by drop-off order (shipment number)
inline int GetFirstUnmarked(bool mark[], int& next)
{
while (mark[next])
next++;
mark[next] = true;
return next;
}
std::string GetRoute(const int R, const int C, const int ord[])
{
int len = R*C-1;
int warehouse[20][20];
warehouse[0][0] = -1;
int rpos = len-1;
bool mark[400] = {};
bool unmark[400] = {};
// Inverse mapping of given order
int invOrd[400];
for (int i = 0; i < len; i++)
invOrd[ord[i]] = i;
// Smallest number not yet assigned
int nextSmallest = 0;
// Last arriving shipment goes at (1,0)
warehouse[0][1] = GetLastUnmarked(mark, ord, rpos);
// Shipment 1 goes at (0,1)
warehouse[1][0] = GetFirstUnmarked(mark, nextSmallest);
// Reserve late shipments for section 3, the smallest of which will go at (1,1)
warehouse[1][1] = R*C;
for (int c = 1; c < C; c++)
{
int last = GetLastUnmarked(mark, ord, rpos);
unmark[last] = true;
warehouse[1][1] = std::min(warehouse[1][1], last);
// Having too many small-numbered shipments in section 3 can be
// problematic, but we can fill it with earlier-arriving shipments in this case
if (c > 1 && last < R)
{
break;
}
}
unmark[warehouse[1][1]] = false;
// Populate sections 1 and 4
for (int r = 2; r < R; r++)
{
warehouse[r][0] = GetFirstUnmarked(mark, nextSmallest);
warehouse[r][1] = GetLastUnmarked(mark, ord, rpos);
}
// Reset shipments reserved for section 3
for (int i = 0; i < len; i++)
{
if (unmark[i])
mark[i] = false;
}
nextSmallest = 0;
rpos = len-1;
// Populate sections 2 and 3
for (int c = 2; c < C; c++)
{
warehouse[0][c] = GetLastUnmarked(mark, ord, rpos);
warehouse[1][c] = GetFirstUnmarked(mark, nextSmallest);
}
// Populate section 5. Shipments go into rows based on drop-off order, columns based on pick-up order
for (int r = 2; r < R; r++)
{
std::pair<int, int> shipments[20];
for (int i = 0; i < C-2; i++)
{
shipments[i].second = GetFirstUnmarked(mark, nextSmallest);
shipments[i].first = -invOrd[shipments[i].second];
}
std::sort(shipments, shipments+C-2);
for (int c = 2; c < C; c++)
{
warehouse[r][c] = shipments[c-2].second;
}
}
// Renumber for sequential pick up
int warehouse2[20][20];
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
warehouse2[r][c] = (r == 0 && c == 0) ? -1 : len-1-invOrd[warehouse[r][c]];
// pick up
std::string part1 = Solve(R, C, warehouse2, 0);
// drop off
std::string part2 = Solve(R, C, warehouse, 1);
return Expand(Undo(part1) + part2);
}
int main()
{
int T;
scanf("%d", &T);
for (int t = 0; t < T; t++)
{
int R, C;
scanf("%d%d", &R, &C);
int ord[400];
int len = R*C-1;
for (int i = 0; i < len; i++)
{
scanf("%d", ord+i);
ord[i]--;
}
std::string route = GetRoute(R, C, ord);
if (R != C)
{
std::string route2 = GetRoute(C, R, ord);
if (route2.length() < route.length())
route = Transpose(route2);
}
printf("%s\n", route.c_str());
}
}