hyinia

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<vector<char> >g;

vector<vector<int> > d;
vector<vector<pair<int,int> > >  t;
int n,m;
int res1=-1,res2=-1;
int dx[] = {-1, -1, -1,  0, 1, 1,  1,  0};
int dy[] = {-1,  0,  1,  1, 1, 0, -1, -1};
void add(int x, int y, int dist, queue<pair<int,int> >&q){
if(isalpha(g[x][y])){
                for(int h=0; h<t[g[x][y]-'A'].size(); h++){
                pair<int,int> newto=t[g[x][y]-'A'][h];

                    q.push(newto);
                  //cout<<newto.first<<newto.second<<' '<<to.first<<to.second<<endl;
                  //cout<<d[to.first][to.second]<<endl;

                    d[newto.first][newto.second]=dist+1;
                  //  cout<<d[newto.first][newto.second]<<' ';
                }
         }

    else{
        d[x][y]=dist+1;
        q.push({x,y});
    }



}
int bfs(int x, int y){
    queue<pair<int,int> > q;
    q.push({x,y});
    while(!q.empty()){

        pair<int,int> to=q.front();
      /*  if(to.first==2 && to.second==0){
            cout<<"=="<<d[to.first][to.second]<<endl;

        }*/

       //cout<<to.first<<' '<<to.second<<endl;
       //cout<<used[0][6]<<' '<<endl;

        if(g[to.first][to.second]=='!'){
            res1=d[to.first][to.second];
        }
        if(g[to.first][to.second]=='$'){
            res2=d[to.first][to.second];
        }
        q.pop();


        for(int i=0; i<8; i++){
            pair<int,int> cop=make_pair(to.first+dx[i], to.second+dy[i]);
                if(cop.first>=0 && cop.first<n && cop.second>=0 && cop.second<m && g[cop.first][cop.second]!='#' && d[cop.first][cop.second]==0){
                    add(cop.first,cop.second,d[cop.first][cop.second],q);

            /*if(cop.first==2 && cop.second==0){
            cout<<"=="<<d[cop.first][cop.second]<<endl;*/


            }
        }

        }
    if(res1==-1 || res2==-1) return -1;
    return(max(res1,res2));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
     t.resize(30,vector<pair<int,int> >());
    g.resize(n,vector<char>(m));
    d.resize(n,vector<int> (m));

    char a;
    pair<int,int> kate,jelo,krep;
    string str;
    for(int i=0; i<n; i++){
        cin>>str;
        for(int j=0; j<str.size(); j++){
            g[i][j]=str[j];
            if(str[j]=='$') kate={i,j};
            else if(str[j]=='!') jelo={i,j};
            else if(str[j]=='*'){ krep={i,j};
            g[i][j]='#';
            }
            else if(isalpha(str[j]))
                t[g[i][j]-'A'].emplace_back(i,j);
        }
    }


        vector<int>ans;
    for(int i=0; i<8; i++){
        pair<int,int> v=make_pair(krep.first+dx[i],krep.second+dy[i]);
        if(v.first>=0 && v.first<n && v.second>=0 && v.second<m && g[v.first][v.second]!='#'){
            ans.pb(bfs(v.first,v.second));
             d.assign(n,vector<int>(m,0));
        }
    }
    int mn=ans[0];
    for(int i=1; i<ans.size(); i++){
        if(mn>ans[i])
            mn=ans[i];
    }
    if(mn==-1 )
        cout<<"Impossible";
    else cout<<++mn;



    return 0;
}