#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("parcare.in");
ofstream fout("parcare.out");
struct car{
char ID;
int length, x, y;
bool isVertical;
int putere;
};
int n, totalCnt=0, currentNumber;;
char v[9][9], vCopy[9][9];
car cars[10];
bitset<282475249> b;
void afisare(bool back){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cout<<v[i][j];
cout<<"\n";
}
if(!back)totalCnt++;
cout<<totalCnt<<' '<<back<<'\n';
}
//void checker(){
// for(int i=0;i<n;i++){
// if(v[0][i]!='#'||v[n][i]!='#')
// cout<<"\n******\n";
// if(v[i][0]!='#'||v[i][n]!='#')
// cout<<"\n******\n";
// }
//}
bool canExit(){
for(int i=cars[0].x-1;i>0;i--)
if(v[i][cars[0].y]!='.')
return false;
return true;
}
void init(){
char id;
int cnt;
for(int i=1;i<n-1;i++)
for(int j=1;j<n-1;j++){
if(vCopy[i][j]=='.')
continue;
id=vCopy[i][j];
vCopy[i][j]='.';
if(vCopy[i][j+1]==id){
cnt=1;
while(vCopy[i][j+cnt]==id){
vCopy[i][j+cnt]='.';
cnt++;
}
cars[id-'A'].ID=id;
cars[id-'A'].isVertical=false;
cars[id-'A'].length=cnt;
cars[id-'A'].x=i;
cars[id-'A'].y=j;
}
else{
cnt=1;
while(vCopy[i+cnt][j]==id){
vCopy[i+cnt][j]='.';
cnt++;
}
cars[id-'A'].ID=id;
cars[id-'A'].isVertical=true;
cars[id-'A'].length=cnt;
cars[id-'A'].x=i;
cars[id-'A'].y=j;
}
}
}
void muta(car & masina, int directie, int dist){
int x, y;
if(directie==1){
x=masina.x;
y=masina.y;
for(int i=0;i<masina.length;i++)
v[x++][y]='.';
x=masina.x-dist;
masina.x=x;
for(int i=0;i<masina.length;i++)
v[x++][y]=masina.ID;
currentNumber-=masina.putere*dist;
}
if(directie==2){
x=masina.x;
y=masina.y;
for(int i=0;i<masina.length;i++)
v[x][y++]='.';
y=masina.y+dist;
masina.y=y;
for(int i=0;i<masina.length;i++)
v[x][y++]=masina.ID;
currentNumber+=masina.putere*dist;
}
if(directie==3){
x=masina.x;
y=masina.y;
for(int i=0;i<masina.length;i++)
v[x++][y]='.';
x=masina.x+dist;
masina.x=x;
for(int i=0;i<masina.length;i++)
v[x++][y]=masina.ID;
currentNumber+=masina.putere*dist;
}
if(directie==4){
x=masina.x;
y=masina.y;
for(int i=0;i<masina.length;i++)
v[x][y++]='.';
y=masina.y-dist;
masina.y=y;
for(int i=0;i<masina.length;i++)
v[x][y++]=masina.ID;
currentNumber-=masina.putere*dist;
}
b.set(currentNumber);
}
int maxDist(car & masina, int dir){
int cnt=0;
if(dir==1){
for(int i=masina.x-1;i>0;i--){
if(v[i][masina.y]!='.')
return cnt;
cnt++;
}
return cnt;
}
if(dir==2){
for(int i=masina.y+masina.length;i<n-1;i++){
if(v[masina.x][i]!='.')
return cnt;
cnt++;
}
return cnt;
}
if(dir==3){
for(int i=masina.x+masina.length;i<n-1;i++){
if(v[i][masina.y]!='.')
return cnt;
cnt++;
}
return cnt;
}
if(dir==4){
for(int i=masina.y-1;i>0;i--){
if(v[masina.x][i]!='.')
return cnt;
cnt++;
}
return cnt;
}
return 5;
}
bool foundSolution=false;
char sol[102][4];
int cntSol=0;
void solver(car & masina, int dir, int dist, int noMove, char last){
// checker();
if(noMove>98)
return;
muta(masina, dir, dist);
//afisare(false);
if(canExit()){
sol[cntSol][0]=masina.ID;
sol[cntSol][1]=(char)dir+'1'-1;
sol[cntSol++][2]=(char)dist+'1'-1;
//cout<<masina.ID<<dir<<dist<<"\n";
foundSolution=true;
return;
}
int d;
for(int i=0;i<10;i++){
if(!cars[i].length)
break;
if(cars[i].ID==masina.ID)
continue;
if(cars[i].isVertical){
for(d=maxDist(cars[i], 1); d>0; d--){
if(b.test(currentNumber-cars[i].putere*d))continue;
solver(cars[i], 1, d, noMove+1, masina.ID);
if(foundSolution){
sol[cntSol][0]=masina.ID;
sol[cntSol][1]=(char)dir+'1'-1;
sol[cntSol++][2]=(char)dist+'1'-1;
//cout<<masina.ID<<dir<<dist<<"\n";
return;
}
}
for(d=maxDist(cars[i], 3);d>=0; d--){
if(b.test(currentNumber+cars[i].putere*d))continue;
solver(cars[i], 3, d, noMove+1, masina.ID);
if(foundSolution){
sol[cntSol][0]=masina.ID;
sol[cntSol][1]=(char)dir+'1'-1;
sol[cntSol++][2]=(char)dist+'1'-1;
//cout<<masina.ID<<dir<<dist<<"\n";
return;
}
}
}
else{
for(d=maxDist(cars[i], 2);d >0;d--){
if(b.test(currentNumber+cars[i].putere*d))continue;
solver(cars[i], 2, d, noMove+1, masina.ID);
if(foundSolution){
sol[cntSol][0]=masina.ID;
sol[cntSol][1]=(char)dir+'1'-1;
sol[cntSol++][2]=(char)dist+'1'-1;
//cout<<masina.ID<<dir<<dist<<"\n";
return;
}
}
for(d=maxDist(cars[i], 4);d>0;d--){
if(b.test(currentNumber-cars[i].putere*d))continue;
solver(cars[i], 4, d, noMove+1, masina.ID);
if(foundSolution){
sol[cntSol][0]=masina.ID;
sol[cntSol][1]=(char)dir+'1'-1;
sol[cntSol++][2]=(char)dist+'1'-1;
//cout<<masina.ID<<dir<<dist<<"\n";
return;
}
}
}
}
if(dir==1)dir=3;
else if(dir==2)dir=4;
else if(dir==3)dir=1;
else if(dir==4)dir=2;
//masina.x=cars[masina.ID-'A'].x;
//masina.y=cars[masina.ID-'A'].y;
muta(masina, dir, dist);
//afisare(true);
}
int main()
{
fin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
fin>>v[i][j];
vCopy[i][j]=v[i][j];
}
init();
int d;
int pc = 1;
for(int i=9;i>-1;i--){
if(!cars[i].length)
continue;
cars[i].putere = pc;
pc *= 7;
if(cars[i].isVertical)
currentNumber += cars[i].putere * cars[i].x;
else currentNumber += cars[i].putere * cars[i].y;
}
b.set(currentNumber);
for(int i=9;i>-1;i--){
if(!cars[i].length)
continue;
if(cars[i].isVertical){
if(d=maxDist(cars[i], 1)){
solver(cars[i], 1, d, 1, -1);
if(foundSolution)
break;
}
if(d=maxDist(cars[i], 3)){
solver(cars[i], 3, d, 1, -1);
if(foundSolution)
break;
}
}
else{
if(d=maxDist(cars[i], 2)){
solver(cars[i], 2, d, 1, -1);
if(foundSolution)
break;
}
if(d=maxDist(cars[i], 4)){
solver(cars[i], 4, d, 1, -1);
if(foundSolution)
break;
}
}
}
fout<<cntSol+1<<"\n";
for(int i=cntSol-1;i>=0;i--){
if(sol[i][1]=='1')sol[i][1]='N';
if(sol[i][1]=='2')sol[i][1]='E';
if(sol[i][1]=='3')sol[i][1]='S';
if(sol[i][1]=='4')sol[i][1]='V';
fout<<sol[i]<<"\n";
}
fout<<"Exit";
return 0;
}