#include 
#include 
#include 
using namespace std;

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

class ChessMaze {
public:
    int traverseMaze(vector 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;iQ;
    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=0&&tj=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**
 
 
 **/