10937

#include <cstdio>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>

#define INF 10000
using namespace std;

int location,target;
vector<vector<int> > dp;
int h,w;
int graph[200][200];
string str[60];

struct POINT{
	int x,y;
};

POINT pp[3030];
POINT src,tr;
int k;
int dirx[4]={1,0,0,-1};
int diry[4]={0,1,-1,0};

int bfs(int s,int t)
{
	int tmpy,tmpx;
	queue<int> q;
	bool visit[55][55];
	int dist[55][55];

	memset(dist,0,sizeof(dist));
	for(int i=0;i<55;i++)
	{
		for(int j=0;j<55;j++)
		{
			dist[i][j]=INF;
			visit[i][j]=false;
		}
	}

	tmpx = pp[s].x;
	tmpy = pp[s].y;

	q.push(tmpx);
	q.push(tmpy);

	visit[tmpx][tmpy]=1;
	dist[tmpx][tmpy]=0;

	while(!q.empty())
	{
		int a = q.front();q.pop();
		int b = q.front();q.pop();

		for(int i=0;i<4;i++)
		{
			int tx = a+dirx[i];
			int ty = b+diry[i];
			if(tx<0 || tx>=h)
			continue;
			if(ty<0 || ty>=w)
			continue;
			if(str[tx][ty]=='#')
			continue;

			if(!visit[tx][ty])
			{
				q.push(tx);q.push(ty);
				visit[tx][ty]=1;
				dist[tx][ty]=dist[a][b]+1;
			}
		}
	}

	return dist[pp[t].x][pp[t].y];
}

int tsp(int status,int location)
{
	if(dp[status][location]!=-1)
	return dp[status][location];

	dp[status][location] = 1e9;

	int mask = 1<<location;

	for(int i=0;i<k;i++)
	{
		if(i!=location && (status & (1<<i)))
		dp[status][location]= min(dp[status][location],tsp(status-mask,i)+graph[i][location]);
	}
	return dp[status][location];
}

int main()
{
	int dx[8]={1,0,0,-1,1,1,-1,-1};
	int dy[8]={0,1,-1,0,1,-1,-1,1};

	while(cin>>h)
	{
		cin>>w;
		if(h+w==0)
		break;

		for(int i=0;i<h;i++)
			cin>>str[i];
		memset(graph,0,sizeof(graph));

		int res = 0;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(str[i][j]=='~')
				{
					str[i][j]='#';
				}
				else if(str[i][j]=='*')
				{
					str[i][j]='#';
					for(int l=0;l<8;l++)
					{
						if(i+dx[l]<0 || i+dx[l]>=h)
						continue;
						if(j+dy[l]<0 || j+dy[l]>=w)
						continue;
						if(str[i+dx[l]][j+dy[l]]=='!' || str[i+dx[l]][j+dy[l]]=='@')
						res = -1;
						if(str[i+dx[l]][j+dy[l]]!='*')
							str[i+dx[l]][j+dy[l]]='#';
					}
				}
			}
		}

		if(res==-1)
		{
			cout<<-1<<"\n";
			continue;
		}
		k = 0;
		location = -1; target = -1;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(str[i][j]=='!')
				{
					pp[k].x = i; pp[k].y = j; k+=1;
				}
				else if(str[i][j]=='@')
				{
					location = k;
					pp[k].x = i; pp[k].y = j; k+=1;
				}
			}
		}

		if(k==1)
		{
			cout<<0<<"\n";
			continue;
		}
		for(int i=0;i<k;i++)
		{
			for(int j=i+1;j<k;j++)
			{
					graph[i][j]=bfs(i,j);
					graph[j][i] = graph[i][j];
			}
		}

		dp = vector< vector< int > >(1<<k,vector<int>(k,-1));
		for(int i=0;i<k;i++)
			dp[1<<i][i]=graph[location][i];

		res = tsp((1<<(k))-1,location);
		if(res>=INF)
		{
			cout<<-1<<"\n";
			continue;
		}
		cout<<res<<"\n";
	}

	return 0;
}