#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

bool vis[16][16][15][(1<<10)];

class ChessMaze {
public:
    int traverseMaze(vector<string> mat) {
    memset(vis,0,sizeof vis);
    int n,m;

        n = mat.size();
        m = mat[0].size();
    int si,sj,ei,ej;
    int b=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(mat[i][j]=='S')
            {
                si=i;
                sj=j;
            }
            if(mat[i][j]=='E')
            {
                ei=i;
                ej=j;
            }
            if(mat[i][j]=='K')
            {
                mat[i][j]= (b+'0');
                b++;
            }
        }
    }
    queue<int>Q;
    Q.push(si);
    Q.push(sj);
    Q.push(0);///K
    Q.push(0);///kojK
    Q.push(0);///kolku
    vis[si][sj][0][0]=true;
    int di[4]={1,-1,0,0};
    int dj[4]={0,0,-1,1};
    int dik[8]={-1,-1,1,1,2,2,-2,-2};
    int djk[8]={-2,2,-2,2,-1,1,-1,1};
    while(!Q.empty())
    {
        int ci=Q.front();
        Q.pop();
        int cj=Q.front();
        Q.pop();
        int k=Q.front();
        Q.pop();
        int kojk=Q.front();
        Q.pop();
        int kolku=Q.front();
        Q.pop();
        if(ci==ei && cj==ej)
        {
            return kolku;
        }
        ///obicno pesacenje
        for(int i=0;i<4;i++)
        {
            int ti=di[i]+ci;
            int tj=dj[i]+cj;
            if(ti>=0&&ti<n&&tj>=0&&tj<m)
            {
                if(mat[ti][tj]=='*')
                {
                    continue;
                }
                if(mat[ti][tj]=='.')
                {
                    if(!vis[ti][tj][k][kojk])
                    {
                        Q.push(ti);
                        Q.push(tj);
                        Q.push(k);
                        Q.push(kojk);
                        Q.push(kolku+1);
                        vis[ti][tj][k][kojk]=true;
                    }
                }
                if(mat[ti][tj]=='E')
                {
                    return kolku + 1;
                }
                if(isdigit(mat[ti][tj]))
                {
                    bool ok=kojk&(1<<(mat[ti][tj]-'0'));
                    if(!ok)
                    {
                        int nkojk=kojk|(1<<(mat[ti][tj]-'0'));
                        if(!vis[ti][tj][k+1][nkojk])
                        {
                            Q.push(ti);
                            Q.push(tj);
                            Q.push(k+1);
                            Q.push(nkojk);
                            Q.push(kolku+1);
                            vis[ti][tj][k+1][nkojk]=true;
                        }
                    }
                    else if(ok)
                    {
                        if(!vis[ti][tj][k][kojk])
                        {
                            Q.push(ti);
                            Q.push(tj);
                            Q.push(k);
                            Q.push(kojk);
                            Q.push(kolku+1);
                            vis[ti][tj][k][kojk]=true;
                        }
                    }
                }
            }
        }
        ///ako imamae konji
        ///
        if(k == 0) continue;
        for(int i=0;i<8;i++)
        {
            int ti=ci+dik[i];
            int tj=cj+djk[i];
            if(ti>=n||ti<0||tj>=m||tj<0||mat[ti][tj]=='*')
            {
                continue;
            }
            if(mat[ti][tj] == 'E') {
                return kolku + 1;
            }
            if(mat[ti][tj]=='.')
            {
                if(!vis[ti][tj][k-1][kojk])
                {
                    Q.push(ti);
                    Q.push(tj);
                    Q.push(k-1);
                    Q.push(kojk);
                    Q.push(kolku+1);
                    vis[ti][tj][k-1][kojk]=true;
                }
            }
            if(isdigit(mat[ti][tj]))
            {
                bool ok=kojk&(1<<(mat[ti][tj]-'0'));
                if(!ok)
                {
                    int nkojk=kojk|(1<<(mat[ti][tj]-'0'));
                    if(!vis[ti][tj][k][nkojk])
                    {
                        Q.push(ti);
                        Q.push(tj);
                        Q.push(k);
                        Q.push(nkojk);
                        Q.push(kolku+1);
                        vis[ti][tj][k][nkojk]=true;
                    }
                }
                else if(ok)
                {
                    if(!vis[ti][tj][k-1][kojk])
                    {
                        Q.push(ti);
                        Q.push(tj);
                        Q.push(k-1);
                        Q.push(kojk);
                        Q.push(kolku+1);
                        vis[ti][tj][k-1][kojk]=true;
                    }
                }
            }
        }
    }

    return -1;
    }
};
/*
 4 5
 ...*.
 ..***
 ...K*
 S*E**


 **/