10944

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>

#define INF 1000
using namespace std;

vector<vector<int> > dp;
int dis[25][25];

struct point{
int x;
int y;
};
point pp[405];
int x,y;
int k;
string s;
bool visit[25];
int location;
int MX;

/*
int trace(int a,int dist)
{
	visit[a]=1;
	bool f=false;
	for(int i=1;i<k;i++)
	{
		if(!visit[i])
		{
			trace(i,dist+dis[a][i]);
			visit[i]=0;
			f=1;
		}
	}
	if(!f)
	{
		int tmp = dist+dis[a][location];
		if(tmp<MX)
		MX = tmp;
	}
	return 0;
}
*/
int tsp(int status,int src)
{
	if(dp[status][src]!=-1)
	return dp[status][src];

	dp[status][src] = 1e9;

	int mask = 1<<src;

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

int main()
{
	while(scanf("%d %d",&x,&y)!=EOF)
	{
		k=0;
		for(int i=0;i<x;i++)
		{
			cin>>s;
			for(int j=0;j<s.size();j++)
			{
				if(s[j]=='L')
				{
					pp[k].x = i;
					pp[k].y = j;
					location = k;
					k++;
				}
				else if(s[j]=='#')
				{
					pp[k].x = i;
					pp[k].y = j;
					k++;
				}
			}
		}

		for(int i=0;i<k;i++)
		{
			for(int j=0;j<k;j++)
			{
				if(i==j)
				dis[i][j] = 0;
				else
				{
					int d = abs(pp[i].x-pp[j].x);
					int dd = abs(pp[i].y-pp[j].y);
					dis[i][j] = max(d,dd);
				}
			}
		}

		/*MX = INF;
		********This is backtrack algo but gets TLE******
		trace(location,0);
		visit[location]=0;
		cout<<MX<<"\n";
		*/
		dp = vector< vector< int > >(1<<k,vector<int>(k,-1));
		for(int i=0;i<k;i++)
			dp[1<<i][i]=dis[location][i];

		cout<<tsp((1<<(k))-1,location)<<"\n";
	}
	return 0;
}