#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define maxinp (int)(1500)
#define MODUL (int)(1e9+57)
#define siz(x) (int)(x.size())
#define len(x) (int)(x.length())
#define whole(x) x.begin(), x.end()
#define FOR(i, x, y) for(int i=x; i<=y; ++i)
#define FORl(i, x, y) for(int i=x; i<y; ++i)
#define FORb(i, x, y) for(int i=x; i>=y; --i)
#define FORlb(i, x, y) for(int i=x; i>y; --i)
#define MEMS(x, val) memset(x, val, sizeof(x))
#define FILEOP(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef queue<ii> qii;
typedef long long ll;
int nextx[4] = {-1, 0, 0, 1};
int nexty[4] = {0, -1, 1, 0};
bool Free[maxinp][maxinp];
int Time[maxinp][maxinp];
char a[maxinp][maxinp];
int m, n, res, nTime;
qii mainq, subq;
ii start[3];
int nInstruction = 0;
void Debug()
{
cout << endl;
FOR(i, 1, m)
{
FOR(j, 1, n)
{
cout << Time[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Enter()
{
int cnt = 1;
MEMS(Free, true);
scanf("%d%d", &m, &n);
FOR(i, 1, m)
{
FOR(j, 1, n)
{
cin >> a[i][j];
if(a[i][j] != 'X')
{
Time[i][j] = 0;
mainq.push(ii(i, j));
if(a[i][j] == 'L')
{
start[cnt] = ii(i, j);
++cnt;
}
Free[i][j] = false;
}
else Time[i][j] = 1234567890;
++nInstruction;
}
}
}
//Check
bool IsValid(int _x, int _y)
{
return(_x >= 1 && _y >= 1 && _x <= m && _y <= n && Free[_x][_y]);
}
void PreProcess()
{
while(!mainq.empty())
{
int curx = mainq.front().first;
int cury = mainq.front().second;
++nInstruction;
mainq.pop();
FOR(i, 0, 3)
{
int x = curx + nextx[i];
int y = cury + nexty[i];
if(IsValid(x, y))
{
if(a[x][y] == 'X')
{
Free[x][y] = false;
mainq.push(ii(x, y));
Time[x][y] = min(Time[x][y], Time[curx][cury] + 1);
}
}
}
}
//Debug();
}
void FloodFill1(ii st1, ii st2)
{
mainq.push(st1);
Free[st1.first][st1.second] = false;
while(!mainq.empty())
{
int curx = mainq.front().first;
int cury = mainq.front().second;
//Time[curx][cury] = nTime;
++nInstruction;
mainq.pop();
FOR(i, 0, 3)
{
int x = curx + nextx[i];
int y = cury + nexty[i];
ii dir = ii(x, y);
if(IsValid(x, y))
{
Free[x][y] = false;
if(dir == st2) return;
if(Time[x][y] <= res) mainq.push(dir);
else subq.push(dir);
}
}
if(mainq.empty())
{
++res;
swap(mainq, subq);
}
}
}
//Process
void Solve()
{
res = 0;
PreProcess();
MEMS(Free, true);
FloodFill1(start[1], start[2]);
printf("%d", res);
cerr << endl;
cerr << nInstruction << endl;
}
//Main Procedure
int main()
{
Enter();
Solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAogCiNkZWZpbmUgdGFzayAiIgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgbWF4aW5wIChpbnQpKDE1MDApCiNkZWZpbmUgTU9EVUwgKGludCkoMWU5KzU3KQojZGVmaW5lIHNpeih4KSAoaW50KSh4LnNpemUoKSkKI2RlZmluZSBsZW4oeCkgKGludCkoeC5sZW5ndGgoKSkKI2RlZmluZSB3aG9sZSh4KSB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSBGT1IoaSwgeCwgeSkgZm9yKGludCBpPXg7IGk8PXk7ICsraSkKI2RlZmluZSBGT1JsKGksIHgsIHkpIGZvcihpbnQgaT14OyBpPHk7ICsraSkKI2RlZmluZSBGT1JiKGksIHgsIHkpIGZvcihpbnQgaT14OyBpPj15OyAtLWkpCiNkZWZpbmUgRk9SbGIoaSwgeCwgeSkgZm9yKGludCBpPXg7IGk+eTsgLS1pKQojZGVmaW5lIE1FTVMoeCwgdmFsKSBtZW1zZXQoeCwgdmFsLCBzaXplb2YoeCkpCiNkZWZpbmUgRklMRU9QKHgpIGZyZW9wZW4oeCIuaW5wIiwgInIiLCBzdGRpbik7IGZyZW9wZW4oeCIub3V0IiwgInciLCBzdGRvdXQpOwp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyB1bGw7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgcXVldWU8aWk+IHFpaTsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CmludCBuZXh0eFs0XSA9IHstMSwgMCwgMCwgMX07CmludCBuZXh0eVs0XSA9IHswLCAtMSwgMSwgMH07CmJvb2wgRnJlZVttYXhpbnBdW21heGlucF07CmludCBUaW1lW21heGlucF1bbWF4aW5wXTsKY2hhciBhW21heGlucF1bbWF4aW5wXTsKaW50IG0sIG4sIHJlcywgblRpbWU7CnFpaSBtYWlucSwgc3VicTsKaWkgc3RhcnRbM107CmludCBuSW5zdHJ1Y3Rpb24gPSAwOwp2b2lkIERlYnVnKCkKewogCiAgICBjb3V0IDw8IGVuZGw7CiAgICBGT1IoaSwgMSwgbSkKICAgIHsKICAgICAgICBGT1IoaiwgMSwgbikKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQgPDwgVGltZVtpXVtqXSA8PCAiICI7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgZW5kbDsKICAgIH0KICAgIGNvdXQgPDwgZW5kbDsKIAogCn0KIAogCnZvaWQgRW50ZXIoKQp7CglpbnQgY250ID0gMTsKCU1FTVMoRnJlZSwgdHJ1ZSk7CiAKIAoJc2NhbmYoIiVkJWQiLCAmbSwgJm4pOwogCiAKIAogCglGT1IoaSwgMSwgbSkKCXsKCSAgICBGT1IoaiwgMSwgbikKCSAgICB7CiAKCSAgICAgICAgY2luID4+IGFbaV1bal07CiAKIAogICAgICAgICAgICBpZihhW2ldW2pdICE9ICdYJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgVGltZVtpXVtqXSA9IDA7CiAKICAgICAgICAgICAgICAgIG1haW5xLnB1c2goaWkoaSwgaikpOwogCiAgICAgICAgICAgICAgICBpZihhW2ldW2pdID09ICdMJykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBzdGFydFtjbnRdID0gaWkoaSwgaik7CiAgICAgICAgICAgICAgICAgICAgKytjbnQ7CiAgICAgICAgICAgICAgICB9CiAKICAgICAgICAgICAgICAgIEZyZWVbaV1bal0gPSBmYWxzZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIFRpbWVbaV1bal0gPSAxMjM0NTY3ODkwOwogCiAgICAgICAgICAgICsrbkluc3RydWN0aW9uOwogCiAKCSAgICB9Cgl9CiAKfQogCi8vQ2hlY2sKYm9vbCBJc1ZhbGlkKGludCBfeCwgaW50IF95KQp7CiAgICByZXR1cm4oX3ggPj0gMSAmJiBfeSA+PSAxICYmIF94IDw9IG0gJiYgX3kgPD0gbiAmJiBGcmVlW194XVtfeV0pOwp9CiAKdm9pZCBQcmVQcm9jZXNzKCkKewogICAgd2hpbGUoIW1haW5xLmVtcHR5KCkpCiAgICB7CiAgICAgICAgaW50IGN1cnggPSBtYWlucS5mcm9udCgpLmZpcnN0OwogICAgICAgIGludCBjdXJ5ID0gbWFpbnEuZnJvbnQoKS5zZWNvbmQ7CiAKICAgICAgICArK25JbnN0cnVjdGlvbjsKICAgICAgICBtYWlucS5wb3AoKTsKIAogICAgICAgIEZPUihpLCAwLCAzKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHggPSBjdXJ4ICsgbmV4dHhbaV07CiAgICAgICAgICAgIGludCB5ID0gY3VyeSArIG5leHR5W2ldOwogCiAgICAgICAgICAgIGlmKElzVmFsaWQoeCwgeSkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKGFbeF1beV0gPT0gJ1gnKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIEZyZWVbeF1beV0gPSBmYWxzZTsKICAgICAgICAgICAgICAgICAgICBtYWlucS5wdXNoKGlpKHgsIHkpKTsKICAgICAgICAgICAgICAgICAgICBUaW1lW3hdW3ldID0gbWluKFRpbWVbeF1beV0sIFRpbWVbY3VyeF1bY3VyeV0gKyAxKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KIAogICAgfQogCiAgICAvL0RlYnVnKCk7CiAKIAogCn0Kdm9pZCBGbG9vZEZpbGwxKGlpIHN0MSwgaWkgc3QyKQp7CiAgICBtYWlucS5wdXNoKHN0MSk7CiAgICBGcmVlW3N0MS5maXJzdF1bc3QxLnNlY29uZF0gPSBmYWxzZTsKICAgIHdoaWxlKCFtYWlucS5lbXB0eSgpKQogICAgewogICAgICAgIGludCBjdXJ4ID0gbWFpbnEuZnJvbnQoKS5maXJzdDsKICAgICAgICBpbnQgY3VyeSA9IG1haW5xLmZyb250KCkuc2Vjb25kOwogCiAgICAgICAgLy9UaW1lW2N1cnhdW2N1cnldID0gblRpbWU7CiAgICAgICAgKytuSW5zdHJ1Y3Rpb247CiAKICAgICAgICBtYWlucS5wb3AoKTsKIAogICAgICAgIEZPUihpLCAwLCAzKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHggPSBjdXJ4ICsgbmV4dHhbaV07CiAgICAgICAgICAgIGludCB5ID0gY3VyeSArIG5leHR5W2ldOwogICAgICAgICAgICBpaSBkaXIgPSBpaSh4LCB5KTsKIAogICAgICAgICAgICBpZihJc1ZhbGlkKHgsIHkpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBGcmVlW3hdW3ldID0gZmFsc2U7CiAgICAgICAgICAgICAgICBpZihkaXIgPT0gc3QyKSByZXR1cm47CiAgICAgICAgICAgICAgICBpZihUaW1lW3hdW3ldIDw9IHJlcykgbWFpbnEucHVzaChkaXIpOwogICAgICAgICAgICAgICAgZWxzZSBzdWJxLnB1c2goZGlyKTsKICAgICAgICAgICAgfQogICAgICAgIH0KIAogICAgICAgIGlmKG1haW5xLmVtcHR5KCkpCiAgICAgICAgewogICAgICAgICAgICArK3JlczsKICAgICAgICAgICAgc3dhcChtYWlucSwgc3VicSk7CiAgICAgICAgfQogCiAgICB9Cn0KIAovL1Byb2Nlc3MKdm9pZCBTb2x2ZSgpCnsKICAgIHJlcyA9IDA7CiAgICBQcmVQcm9jZXNzKCk7CiAgICBNRU1TKEZyZWUsIHRydWUpOwogICAgRmxvb2RGaWxsMShzdGFydFsxXSwgc3RhcnRbMl0pOwogICAgcHJpbnRmKCIlZCIsIHJlcyk7CiAKIAogICAgY2VyciA8PCBlbmRsOwogICAgY2VyciA8PCBuSW5zdHJ1Y3Rpb24gPDwgZW5kbDsKIAp9CiAKLy9NYWluIFByb2NlZHVyZQppbnQgbWFpbigpCnsKICAgIEVudGVyKCk7CiAgICBTb2x2ZSgpOwogICAgcmV0dXJuIDA7Cn0g