#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<vector>#include<queue>using namespace std;typedef long long lld;#define pb push_back#define mp make_pair#define X first#define Y second#define inf 0xfffffffint n,m;char g[110][110];bool inside(int x,int y){if(x < 0 || x >= n || y < 0 || y >= m)return false;return true;}struct Node{int a,b,c,mask;Node(){}Node(int a0,int b0,int c0,int mask0){a=a0;b=b0;c=c0;mask=mask0;}};char str[110];queue<Node>Q;int dis[10][10][10][10][2][10][1<<5];int tx[4]={1,-1,0,0};int ty[4]={0,0,1,-1};int af,sf;int id[110][110];int T;int bfs(){while(!Q.empty()){Node o=Q.front();Q.pop();int ax,ay,bx,by,cx,cy,ck,mask;ax=o.a/10;ay=o.a%10;bx=o.b/10;by=o.b%10;if(af == 0){cx=o.c%10;cy=sf;}else{cx=sf;cy=o.c%10;}int c01=o.c/10;int cat=o.c%10;mask=o.mask;ck=o.c/10+af;for(int k=0;k<4;k++){int x1=ax+tx[k];int y1=ay+ty[k];if(!inside(x1,y1) || g[x1][y1] == 'R' ||(x1 == bx && y1 == by) || (x1 == cx && y1 == cy))continue;int tk=k^1;int x2=bx+tx[tk];int y2=by+ty[tk];if(!inside(x2,y2) || g[x2][y2] == 'R' ||(x2 == x1 && y2 == y1) || (x2 == cx && y2 == cy)){x2=bx;y2=by;}int next=mask;if(id[x1][y1] != -1)next|=(1<<id[x1][y1]);if(g[x1][y1] == 'E' && g[x2][y2] == 'E' && (x1 != x2 || y1 != y2)){if(next == ((1<<T)-1))return dis[ax][ay][bx][by][c01][cat][mask]+1;continue;}int x3=cx+tx[ck];int y3=cy+ty[ck];int nc01=c01;if(!inside(x3,y3) || g[x3][y3] == 'R'){x3=cx;y3=cy;nc01^=1;}else{if((x3 == x1 && y3 == y1) || (x3 == x2 && y3 == y2))continue;}int ncat;if(af == 0)ncat=x3;elsencat=y3;if(dis[x1][y1][x2][y2][nc01][ncat][next] == -1){dis[x1][y1][x2][y2][nc01][ncat][next]=dis[ax][ay][bx][by][c01][cat][mask]+1;Q.push(Node(x1*10+y1,x2*10+y2,nc01*10+ncat,next));}}}return -1;}int main(){while(scanf("%d %d",&n,&m)!=EOF){for(int i=0;i<n;i++)scanf("%s",g[i]);int ax,ay,bx,by,c,cx,cy,f;T=0;memset(id,-1,sizeof(id));for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(g[i][j] == 'A'){ax=i;ay=j;}if(g[i][j] == 'B'){bx=i;by=j;}if(g[i][j] == 'K'){cx=i;cy=j;}if(g[i][j] == 'M')id[i][j]=T++;}scanf("%s",str);if(str[0] == 'N' || str[0] == 'S')c=cx,sf=cy;elsec=cy,sf=cx;if(str[0] == 'S')f=0,af=0;if(str[0] == 'N')f=1,af=0;if(str[0] == 'E')f=0,af=2;if(str[0] == 'W')f=1,af=2;memset(dis,-1,sizeof(dis));dis[ax][ay][bx][by][f][c][0]=0;while(!Q.empty())Q.pop();Q.push(Node(ax*10+ay,bx*10+by,f*10+c,0));printf("%dn",bfs());}return 0;}
