//============================================================================
// Name : ACM.cpp
// Author : Tarango Khan
// Copyright : All Rights Reserved By Team Byteheads
// Description : !!!Hello World!!!
//============================================================================
#include <bits/stdc++.h>
#include <stdio.h>
#include <cstring>
using namespace std;
#define Pi 3.14159265359
#define Max 9999999
#define start_pos 15
int N;
char M[22][22];
int row, col;
int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[] = { 0, 0, 1, -1, -1, 1, 1, -1 };
int food = 0, sx, sy;
int Set(int N, int pos) {
return N = N | (1 << pos);
}
bool Check(int N, int pos) {
return (bool) (N & (1 << pos));
}
map<int, pair<int, int> > Map;
int total_nut = 0;
int isValid(int r, int c) {
if (r < 0 || c < 0 || r >= row || c >= col){
return 0;
}
return 1;
}
struct point {
int x;
int y;
int cnt;
point(int a, int b, int c) {
x = a;
y = b;
cnt = c;
}
};
int taken[22][22];
int shortest_Path(int sR, int sC, int tR, int tC) {
memset(taken, 0, sizeof(taken));
queue<point> Q;
Q.push(point(sR, sC, 0));
taken[sR][sC] = 1;
while (Q.empty() == false) {
point cur = Q.front();
Q.pop();
if (cur.x == tR && cur.y == tC) {
return cur.cnt;
}
for (int i = 0; i < 8; i++) {
int xx = cur.x + dx[i];
int yy = cur.y + dy[i];
if (isValid(xx, yy) == 1 && taken[xx][yy] == 0) {
taken[xx][yy] = 1;
Q.push(point(xx, yy, cur.cnt + 1));
}
}
}
return 0;
}
int distances[17][17];
void calculate_path() {
for (int i = 0; i < total_nut; i++) {
for (int j = 0; j < total_nut; j++) {
distances[i][j] = distances[j][i] = shortest_Path(Map[i].first,
Map[i].second, Map[j].first, Map[j].second);
}
distances[i][15] = distances[15][i] = shortest_Path(Map[i].first,Map[i].second, sx, sy);
}
}
int DP[70000][17];
int call(int mask, int r, int c, int pos) {
//printf("Currently at row: %d , col: %d mask: %d\n",r,c,mask);
if (mask == (1 << total_nut) - 1) {
int ed = distances[pos][start_pos];
//printf("\nEnded at r: %d , c: %d for %d\n\n",r,c,ed);
return DP[mask][pos] = ed;
}
if (pos != start_pos){
if (DP[mask][pos] != -1) {
return DP[mask][pos];
}
}
int dist = Max;
//One by one trying to select next # to take
for (int i = 0; i < total_nut; i++) {
if (Check(mask, i) == 0) {
//printf("Taking hash: %d where r: %d , c: %d\n",i,Map[i].first,Map[i].second);
int total_cost = call(Set(mask, i), Map[i].first, Map[i].second, i) + distances[pos][i];
//printf("...At this step, res: %d...\n",total_cost);
dist = min(dist, total_cost);
}
}
//printf("\nFinally at row: %d , col: %d mask: %d , cost: %d\n\n",r,c,mask,dist);
if (dist != Max && pos != start_pos) {
return DP[mask][pos] = dist;
}
return dist;
}
int main() {
while (scanf("%d %d", &row, &col) == 2) {
total_nut = 0;
getchar();
for(int i = 0;i<row;i++){
gets(M[i]);
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (M[i][j] == 'L') {
sx = i;
sy = j;
}
//Saving in Map where we find #
if (M[i][j] == '#') {
pair<int, int> P;
P.first = i;
P.second = j;
Map[total_nut] = P;
total_nut++;
}
}
}
calculate_path();
memset(DP, -1, sizeof(DP));
int res = call(0, sx, sy, start_pos);
printf("%d\n", res);
}
return 0;
}
Ly89PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIE5hbWUgICAgICAgIDogQUNNLmNwcAovLyBBdXRob3IgICAgICA6IFRhcmFuZ28gS2hhbgovLyBDb3B5cmlnaHQgICA6IEFsbCBSaWdodHMgUmVzZXJ2ZWQgQnkgVGVhbSBCeXRlaGVhZHMKLy8gRGVzY3JpcHRpb24gOiAhISFIZWxsbyBXb3JsZCEhIQovLz09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPGNzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgUGkgMy4xNDE1OTI2NTM1OQojZGVmaW5lIE1heCA5OTk5OTk5CiNkZWZpbmUgc3RhcnRfcG9zIDE1CgppbnQgTjsKCmNoYXIgTVsyMl1bMjJdOwppbnQgcm93LCBjb2w7CmludCBkeFtdID0geyAxLCAtMSwgMCwgMCwgMSwgLTEsIDEsIC0xIH07CmludCBkeVtdID0geyAwLCAwLCAxLCAtMSwgLTEsIDEsIDEsIC0xIH07CmludCBmb29kID0gMCwgc3gsIHN5OwoKaW50IFNldChpbnQgTiwgaW50IHBvcykgewoJcmV0dXJuIE4gPSBOIHwgKDEgPDwgcG9zKTsKfQpib29sIENoZWNrKGludCBOLCBpbnQgcG9zKSB7CglyZXR1cm4gKGJvb2wpIChOICYgKDEgPDwgcG9zKSk7Cn0KbWFwPGludCwgcGFpcjxpbnQsIGludD4gPiBNYXA7CmludCB0b3RhbF9udXQgPSAwOwoKaW50IGlzVmFsaWQoaW50IHIsIGludCBjKSB7CglpZiAociA8IDAgfHwgYyA8IDAgfHwgciA+PSByb3cgfHwgYyA+PSBjb2wpewoJCXJldHVybiAwOwoJfQoJcmV0dXJuIDE7Cn0KCnN0cnVjdCBwb2ludCB7CglpbnQgeDsKCWludCB5OwoJaW50IGNudDsKCXBvaW50KGludCBhLCBpbnQgYiwgaW50IGMpIHsKCQl4ID0gYTsKCQl5ID0gYjsKCQljbnQgPSBjOwoJfQp9OwoKaW50IHRha2VuWzIyXVsyMl07CmludCBzaG9ydGVzdF9QYXRoKGludCBzUiwgaW50IHNDLCBpbnQgdFIsIGludCB0QykgewoJbWVtc2V0KHRha2VuLCAwLCBzaXplb2YodGFrZW4pKTsKCXF1ZXVlPHBvaW50PiBROwoJUS5wdXNoKHBvaW50KHNSLCBzQywgMCkpOwoJdGFrZW5bc1JdW3NDXSA9IDE7CgoJd2hpbGUgKFEuZW1wdHkoKSA9PSBmYWxzZSkgewoJCXBvaW50IGN1ciA9IFEuZnJvbnQoKTsKCQlRLnBvcCgpOwoJCWlmIChjdXIueCA9PSB0UiAmJiBjdXIueSA9PSB0QykgewoJCQlyZXR1cm4gY3VyLmNudDsKCQl9CgkJZm9yIChpbnQgaSA9IDA7IGkgPCA4OyBpKyspIHsKCQkJaW50IHh4ID0gY3VyLnggKyBkeFtpXTsKCQkJaW50IHl5ID0gY3VyLnkgKyBkeVtpXTsKCgkJCWlmIChpc1ZhbGlkKHh4LCB5eSkgPT0gMSAmJiB0YWtlblt4eF1beXldID09IDApIHsKCQkJCXRha2VuW3h4XVt5eV0gPSAxOwoJCQkJUS5wdXNoKHBvaW50KHh4LCB5eSwgY3VyLmNudCArIDEpKTsKCQkJfQoJCX0KCX0KCXJldHVybiAwOwp9CgppbnQgZGlzdGFuY2VzWzE3XVsxN107Cgp2b2lkIGNhbGN1bGF0ZV9wYXRoKCkgewoJZm9yIChpbnQgaSA9IDA7IGkgPCB0b3RhbF9udXQ7IGkrKykgewoJCWZvciAoaW50IGogPSAwOyBqIDwgdG90YWxfbnV0OyBqKyspIHsKCQkJZGlzdGFuY2VzW2ldW2pdID0gZGlzdGFuY2VzW2pdW2ldID0gc2hvcnRlc3RfUGF0aChNYXBbaV0uZmlyc3QsCgkJCQkJTWFwW2ldLnNlY29uZCwgTWFwW2pdLmZpcnN0LCBNYXBbal0uc2Vjb25kKTsKCQl9CgkJZGlzdGFuY2VzW2ldWzE1XSA9IGRpc3RhbmNlc1sxNV1baV0gPSBzaG9ydGVzdF9QYXRoKE1hcFtpXS5maXJzdCxNYXBbaV0uc2Vjb25kLCBzeCwgc3kpOwoJfQp9CgppbnQgRFBbNzAwMDBdWzE3XTsKCmludCBjYWxsKGludCBtYXNrLCBpbnQgciwgaW50IGMsIGludCBwb3MpIHsKCS8vcHJpbnRmKCJDdXJyZW50bHkgYXQgcm93OiAlZCAsIGNvbDogJWQgbWFzazogJWRcbiIscixjLG1hc2spOwoJaWYgKG1hc2sgPT0gKDEgPDwgdG90YWxfbnV0KSAtIDEpIHsKCQlpbnQgZWQgPSBkaXN0YW5jZXNbcG9zXVtzdGFydF9wb3NdOwoJCS8vcHJpbnRmKCJcbkVuZGVkIGF0IHI6ICVkICwgYzogJWQgZm9yICVkXG5cbiIscixjLGVkKTsKCQlyZXR1cm4gRFBbbWFza11bcG9zXSA9IGVkOwoJfQoJaWYgKHBvcyAhPSBzdGFydF9wb3MpewoJCWlmIChEUFttYXNrXVtwb3NdICE9IC0xKSB7CgkJCXJldHVybiBEUFttYXNrXVtwb3NdOwoJCX0KCX0KCWludCBkaXN0ID0gTWF4OwoJLy9PbmUgYnkgb25lIHRyeWluZyB0byBzZWxlY3QgbmV4dCAjIHRvIHRha2UKCWZvciAoaW50IGkgPSAwOyBpIDwgdG90YWxfbnV0OyBpKyspIHsKCQlpZiAoQ2hlY2sobWFzaywgaSkgPT0gMCkgewoJCQkvL3ByaW50ZigiVGFraW5nIGhhc2g6ICVkIHdoZXJlIHI6ICVkICwgYzogJWRcbiIsaSxNYXBbaV0uZmlyc3QsTWFwW2ldLnNlY29uZCk7CgkJCWludCB0b3RhbF9jb3N0ID0gY2FsbChTZXQobWFzaywgaSksIE1hcFtpXS5maXJzdCwgTWFwW2ldLnNlY29uZCwgaSkJKyBkaXN0YW5jZXNbcG9zXVtpXTsKCQkJLy9wcmludGYoIi4uLkF0IHRoaXMgc3RlcCwgcmVzOiAlZC4uLlxuIix0b3RhbF9jb3N0KTsKCQkJZGlzdCA9IG1pbihkaXN0LCB0b3RhbF9jb3N0KTsKCQl9Cgl9CgkvL3ByaW50ZigiXG5GaW5hbGx5IGF0IHJvdzogJWQgLCBjb2w6ICVkIG1hc2s6ICVkICwgY29zdDogJWRcblxuIixyLGMsbWFzayxkaXN0KTsKCWlmIChkaXN0ICE9IE1heCAmJiBwb3MgIT0gc3RhcnRfcG9zKSB7CgkJcmV0dXJuIERQW21hc2tdW3Bvc10gPSBkaXN0OwoJfQoJcmV0dXJuIGRpc3Q7Cn0KCmludCBtYWluKCkgewoJd2hpbGUgKHNjYW5mKCIlZCAlZCIsICZyb3csICZjb2wpID09IDIpIHsKCQl0b3RhbF9udXQgPSAwOwoJCWdldGNoYXIoKTsKCQlmb3IoaW50IGkgPSAwO2k8cm93O2krKyl7CgkJCWdldHMoTVtpXSk7CgkJfQoJCWZvciAoaW50IGkgPSAwOyBpIDwgcm93OyBpKyspIHsKCQkJZm9yIChpbnQgaiA9IDA7IGogPCBjb2w7IGorKykgewoJCQkJaWYgKE1baV1bal0gPT0gJ0wnKSB7CgkJCQkJc3ggPSBpOwoJCQkJCXN5ID0gajsKCQkJCX0KCQkJCS8vU2F2aW5nIGluIE1hcCB3aGVyZSB3ZSBmaW5kICMKCQkJCWlmIChNW2ldW2pdID09ICcjJykgewoJCQkJCXBhaXI8aW50LCBpbnQ+IFA7CgkJCQkJUC5maXJzdCA9IGk7CgkJCQkJUC5zZWNvbmQgPSBqOwoJCQkJCU1hcFt0b3RhbF9udXRdID0gUDsKCQkJCQl0b3RhbF9udXQrKzsKCQkJCX0KCQkJfQoJCX0KCQljYWxjdWxhdGVfcGF0aCgpOwoJCW1lbXNldChEUCwgLTEsIHNpemVvZihEUCkpOwoJCWludCByZXMgPSBjYWxsKDAsIHN4LCBzeSwgc3RhcnRfcG9zKTsKCQlwcmludGYoIiVkXG4iLCByZXMpOwoJfQoJcmV0dXJuIDA7Cn0K