Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const dx:array[1..4] of shortint=(-1,0,1,0);
      dy:array[1..4] of shortint=(0,1,0,-1);
var m,n,re,i,j,nump,min:longint;
    a:array[1..20,1..20] of char;
    b:array[0..10,0..10] of longint;
    p:array[0..11,0..1] of longint;
    q:array[1..410,0..1] of longint;
    d,dau:array[1..20,1..20] of byte;
    d1:array[1..11] of byte;
    kt:boolean;

function check(x,y:longint):boolean;
begin
     check:=(x>0) and (y>0) and (x<=m) and (y<=n) and (a[x,y]<>'x');
end;

procedure bfs(k,nump:longint);
var num,i,j,x,y,t:longint;
begin
     fillchar(d,sizeof(d),0);
     q[1,0]:=p[k,0]; q[1,1]:=p[k,1];
     d[q[1,0],q[1,1]]:=1;
     num:=1; i:=1; t:=nump;
     repeat
           for j:=1 to 4 do
           begin
                x:=q[i,0]+dx[j]; y:=q[i,1]+dy[j];
                if check(x,y) and (d[x,y]=0) then
                begin
                     inc(num);
                     q[num,0]:=x;
                     q[num,1]:=y;
                     d[x,y]:=d[q[i,0],q[i,1]]+1;
                     if a[x,y]='*' then
                     begin
                          if k=0 then
                          begin
                               dec(t);
                               p[nump-t,0]:=x;
                               p[nump-t,1]:=y;
                               b[0,nump-t]:=d[x,y]-1;
                               b[nump-t,0]:=d[x,y]-1;
                               dau[x,y]:=nump-t;
                          end
                          else
                          begin
                               if dau[x,y]>k then
                               begin
                                    b[k,dau[x,y]]:=d[x,y]-1;
                                    b[dau[x,y],k]:=d[x,y]-1;
                               end;
                          end;
                     end;
                end;
           end;
           inc(i);
     until (i>num) or (t=0);
     kt:=(t=0);
end;

procedure att(i,j:byte);
var k:byte;
begin
     if re>=min then exit;
     if i>nump+1 then
     begin
          if re<min then min:=re;
     end
     else
     begin
          for k:=1 to nump do
              if (d1[k]=0) and (b[k,j]<>0) then
              begin
                   d1[k]:=1;
                   re:=re+b[j,k];
                   att(i+1,k);
                   d1[k]:=0;
                   re:=re-b[j,k];
              end;
     end;
end;

begin
     readln(n,m);
     while n<>0 do
     begin
          nump:=0; min:=maxlongint;
          fillchar(b,sizeof(b),0);
          fillchar(dau,sizeof(dau),0);
          for i:=1 to m do
          begin
               for j:=1 to n do
               begin
                    read(a[i,j]);
                    if a[i,j]='o' then
                    begin
                         p[0,0]:=i; p[0,1]:=j;
                    end;
                    if a[i,j]='*' then inc(nump);
               end;
               readln;
          end;
          bfs(0,nump);
          if not kt then writeln(-1)
          else
          begin
               for i:=1 to nump do bfs(i,nump);
               re:=0;
               fillchar(d1,sizeof(d1),0);
               att(2,0);
               writeln(min);
          end;
          readln(n,m);
     end;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 22
char mat[N][N];
int dis[N][N][N], f[1 << 11][N], n, m;
int qu[2*N*N], lo, hi, x[12], y[12], dirt, robotx, roboty;
bool vst[N][N];
int d[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

bool enter() {
    if(scanf("%d%d", &n, &m) == EOF || n == 0 || m == 0) return 0;
    for(int i = 0; i < m; ++i) scanf("%s", mat[i]);
    return 1;
}

void bfs(int i) {
    lo = hi = 0; qu[hi++] = x[i]; qu[hi++] = y[i];
    memset(vst, 0, sizeof vst); vst[x[i]][y[i]] = 1;
    for(int step = 0; lo != hi; ++step) {
        //printf("%d %d\n", lo, hi);
        for(int k = (hi-lo)/2; k > 0; --k) {
            int x = qu[lo++], y = qu[lo++];
            dis[i][x][y] = step;
            //printf("%d %d %d %d\n", i, x, y, step);
            for(int j = 0; j < 4; ++j) {
                int xx = x + d[j][0], yy = y + d[j][1];
                if(xx >= 0 && xx < m && yy >= 0 && yy < n && !vst[xx][yy] && mat[xx][yy] != 'x') {
                    //printf("%d %d %d %d\n", x, y, xx, yy);
                    vst[xx][yy] = 1;
                    qu[hi++] = xx; qu[hi++] = yy;
                    //printf("%d %d\n", lo, hi);
                }
            }
        }
    }
    //printf("BFS(%d)\n", i);
}

inline int F(int state, int t) {
    int & res = f[state][t];
    if(res != -1) return res;
    if(state == 0) return res = dis[t][robotx][roboty];
    res = 1 << 30;
    for(int i = 0; i < dirt; ++i) if(state & 1 << i && dis[t][x[i]][y[i]] != -1)
        res = min(res, max(dis[t][x[i]][y[i]] + F(state & ~(1 << i), i), -1));
    return res;
}

void solve() {
    dirt = 0; bool findRob = 0;
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            if(mat[i][j] == '*') { x[dirt] = i; y[dirt++] = j; }
            else if(mat[i][j] == 'o') { robotx = i; roboty = j; findRob = 1; }
    if(dirt == 0) { printf("0\n"); return; }
    if(!findRob) { printf("-1\n"); return; }
    //for(int i = 0; i < dirt; ++i) printf("Dirt: %d %d\n", x[i], y[i]);
    memset(dis, -1, sizeof dis);
    for(int i = 0; i < dirt; ++i) bfs(i);
    /*for(int i = 0; i < dirt; ++i) {
        for(int x = 0; x < m; ++x) {
            for(int y = 0; y < n; ++y) printf("%d ", dis[i][x][y]);
            putchar(10);
        }
        putchar(10);
    }*/
    memset(f, -1, sizeof f);
    int res = 1 << 30;
    for(int i = 0; i < dirt; ++i)
        res = min(res, F((1 << dirt) - 1 & ~(1 << i), i));
    printf("%d\n", res == 1 << 30 ? -1 : res);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    while(enter()) solve();
    return 0;
}

Code mẫu của ladpro98

program mclean;//bfs+bitwise
uses    math;
type    e=record
        x,y,p:longint;
        end;

const   wall = 100;
        free = 0;
        maxn = 22;
        maxV = 1 shl 10;
        fi = '';
        dx:array[1..4] of longint = (1,-1,0,0);
        dy:array[1..4] of longint = (0,0,1,-1);
var     n,m,d:longint;
        s:e;
        a:array[1..maxn,1..maxn] of longint;
        check:array[1..maxn,1..maxn] of boolean;
        visit:array[1..maxn,1..maxn,0..maxV] of boolean;
        res:array[1..maxn,1..maxn,0..maxV] of longint;
        //trace:array[1..maxn,1..maxn,0..maxV] of e;
        trash:array[1..maxn] of e;
        q:array[1..maxn*maxn*maxV] of e;
        inp:text;
        done:boolean;

procedure input;
var
        i,j:longint;
        c:char;
begin
        readln(inp,n,m);
        done:=false;
        if (m=0) then halt;
        d:=0;
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                read(inp,c);
                if (c='.') then
                        a[i,j] := free
                else if c='x' then
                        a[i,j] := wall
                else if c='*' then
                begin
                        inc(d);
                        a[i,j] := d;
                        trash[d].x := i;
                        trash[d].y := j;
                end
                else
                if c='o' then
                begin
                        s.x:=i;
                        s.y:=j;
                        a[i,j]:=free;
                end;
                end;
                readln(inp);
        end;

end;

function getbit(i,j:longint):longint;
begin
        exit(i shr (j-1) and 1);
end;


function outBound(i,j:longint):boolean;
begin
        exit(not ((1<=i) and (i<=m) and (1<=j) and (j<=n)));
end;
procedure bfs1;
var     l,r,i,x,y:longint;
        u:e;
begin
        l:=1;r:=1;
        q[1].x:=s.x;
        q[1].y:=s.y;
        check[s.x,s.y]:=true;
        while l<=r do
        begin
                u:=q[l];inc(l);
                for i:=1 to 4 do
                begin
                        x:=u.x+dx[i];
                        y:=u.y+dy[i];
                        if (outBound(x,y)) or (a[x,y] = wall) then continue;
                        if not check[x,y] then
                        begin
                                check[x,y]:=true;
                                inc(r);
                                q[r].x:=x;
                                q[r].y:=y;
                        end;
                end;

        end;
end;

procedure bfs2;
var     l,r,i,x,y,p:longint;
        u:e;
begin
        l:=1;r:=1;
        q[1].x:=s.x;
        q[1].y:=s.y;
        q[1].p:=0;
        visit[s.x,s.y,0]:=true;
        res[s.x,s.y,0]:=0;
        while l<=r do
        begin
                u:=q[l];inc(l);
                for i:=1 to 4 do
                begin
                        x:=u.x+dx[i];
                        y:=u.y+dy[i];
                        if outBound(x,y) or (a[x,y]=wall) then continue;
                        if ((a[x,y]>free) and (getbit(u.p,a[x,y])=0)) then
                                p:=u.p+(1 shl (a[x,y]-1))
                        else    p:=u.p;
                        if not visit[x,y,p] then
                        begin
                                visit[x,y,p]:=true;
                                inc(r);
                                q[r].x:=x;
                                q[r].y:=y;
                                q[r].p:=p;
                                res[x,y,p]:=res[u.x,u.y,u.p]+1;
                                //trace[x,y,p]:=u;
                        end;

                end;

        end;
end;

procedure process;
var     i:longint;
begin
        fillchar(check,sizeof(check),false);
        fillchar(visit,sizeof(visit),false);
        bfs1;
        for i:=1 to d do
        if not check[trash[i].x,trash[i].y] then
        begin
                writeln(-1);
                done:=true;
                exit;
        end
        else
        bfs2;

end;

procedure output;
var     i,r,k,j,t,pos:longint;
        ii:e;
        oup:text;
begin
        if done then exit;
        r:=123456789;
        k:=1 shl d-1;
        for i:=1 to d do
        begin
                if r>res[trash[i].x,trash[i].y,k] then
                begin
                r:=res[trash[i].x,trash[i].y,k];
                pos:=i;
                end;
        end;
        if r=123456789 then writeln(0)
        else
        writeln(r);
        {assign(oup,'mclean.out');
        rewrite(oup);
        i:=trash[pos].x;
        j:=trash[pos].y;
        t:=k;
        while t>0 do
        begin
                writeln(oup,i,' ',j);
                ii:=trace[i,j,t];
                i:=ii.x;
                j:=ii.y;
                t:=ii.p
        end;
        close(oup);}
end;

begin

        assign(inp,fi);
        reset(inp);
        repeat
                input;
                process;
                output;
        until false;
        close(inp);
end.

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
const
  FINP='';
  FOUT='';
  MAXN=25;
  oo=1000000000;
  di:array[1..4] of longint=(-1,1,0,0);
  dj:array[1..4] of longint=(0,0,-1,1);
var
  lt2:array[1..11] of longint;
  a:array[1..MAXN,1..MAXN] of char;
  tt,xet:array[1..MAXN,1..MAXN] of longint;
  qu,qv:array[1..MAXN*MAXN] of longint;
  x,y:array[0..10] of longint;
  c:array[0..10,0..10] of longint;
  hpos,d:array[0..MAXN,0..2048] of longint;
  hu,hm:array[1..MAXN*2048] of longint;
  hsize,sl,m,n:longint;
  f1,f2:text;
  ok:boolean;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure prepare; inline;
var
  i:longint;
begin
  lt2[1]:=2;
  for i:=2 to 11 do
    lt2[i]:=lt2[i-1]*2;
end;
procedure inp;
var
  i,j:longint;
begin
  sl:=0;
  for i:=1 to m do
    begin
      for j:=1 to n do
        begin
          read(f1,a[i,j]);
          case a[i,j] of
            'o': begin x[0]:=i; y[0]:=j; end;
            '*': begin inc(sl); x[sl]:=i; y[sl]:=j; tt[i,j]:=sl; end;
          end;
        end;
      readln(f1);
    end;
end;
procedure bfs(u,v:longint); inline;
var
  first,last,h,uu,vv:longint;
begin
  first:=1; last:=1; qu[1]:=u; qv[1]:=v;
  xet[u,v]:=1;
  while first<=last do
    begin
      u:=qu[first]; v:=qv[first]; inc(first);
      for h:=1 to 4 do
        begin
          uu:=u+di[h]; vv:=v+dj[h];
          if (uu>0) and (uu<=m) and (vv>0) and (vv<=n) and
             (a[uu,vv]<>'x') and (xet[uu,vv]=0) then
            begin
              xet[uu,vv]:=xet[u,v]+1;
              inc(last); qu[last]:=uu; qv[last]:=vv;
            end;
        end;
    end;
end;
procedure init; inline;
var
  i,j,mask:longint;
begin
  for i:=0 to sl do
    begin
      fillchar(xet,sizeof(xet),0);
      bfs(x[i],y[i]);
      for j:=0 to sl do
        if xet[x[j],y[j]]=0 then ok:=false
        else c[i,j]:=xet[x[j],y[j]]-1;
    end;
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[hu[j+1],hm[j+1]]<d[hu[j],hm[j]]) then inc(j);
      if (d[hu[j],hm[j]]<d[hu[i],hm[i]]) then
        begin
          swap(hpos[hu[i],hm[i]],hpos[hu[j],hm[j]]);
          swap(hu[i],hu[j]);
          swap(hm[i],hm[j]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (d[hu[i],hm[i]]<d[hu[j],hm[j]]) do
    begin
      swap(hpos[hu[i],hm[i]],hpos[hu[j],hm[j]]);
      swap(hu[i],hu[j]);
      swap(hm[i],hm[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u,m:longint); inline;
begin
  inc(hsize); hpos[u,m]:=hsize;
  hu[hsize]:=u; hm[hsize]:=m;
  upHeap(hsize);
end;
procedure pop(var u,m:longint); inline;
begin
  u:=hu[1]; m:=hm[1]; hpos[u,m]:=0;
  swap(hu[1],hu[hsize]);
  swap(hm[1],hm[hsize]);
  dec(hsize); downHeap(1);
end;
procedure solve;
var
  u,v,t,tt,i:longint;
begin
  for u:=0 to sl do
  for t:=lt2[sl]-1 downto 0 do
    d[u,t]:=oo;
  fillchar(hpos,sizeof(hpos),0);
  d[0,lt2[sl]-1]:=0;
  hsize:=0;
  push(0,lt2[sl]-1);
  while hsize>0 do
    begin
      pop(u,t);
      if t=0 then
        begin
          writeln(f2,d[u,t]);
          exit;
        end;
      for v:=1 to sl do
      if (t shr (v-1)) and 1=1 then
        begin
          tt:=t and (lt2[sl]-1 shl (v-1)-1);
          if d[v,tt]>d[u,t]+c[u,v] then
            begin
              d[v,tt]:=d[u,t]+c[u,v];
              if hpos[v,tt]=0 then push(v,tt)
              else upHeap(hpos[v,tt]);
            end;
        end;
    end;
end;
begin
  openF;
  prepare;
  readln(f1,n,m);
  while (m>0) and (n>0) do
    begin
      ok:=true;
      inp;
      init;
      if ok then solve
      else writeln(f2,-1);
      readln(f1,n,m);
    end;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
//typedef long double ld;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(int i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(int i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0.0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, 0, -1, +1};
const int dc[] = {-1, +1, 0, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ld eps = ld(1e-9);
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 12

II P, A[maxn];
string s[22];
int n, m;
int d[maxn], a[maxn][maxn];
int f[1 << maxn][maxn];
II que[25 * 25];
int size;

bool thoaman(int r, int c){
    return (r >= 0 && r < n && c >= 0 && c < m && s[r][c] != 'x');
}

int bfs(II start, II finish){
    size = 0;
    int flag[25][25];
    ms(flag, -1);
    que[size++] = start;
    flag[start.fi][start.se] = 0;
    int r, c, rr, cc;
    Rep(i, size){
        r = que[i].fi; c = que[i].se;
        if(que[i] == finish) return flag[r][c];
        Rep(h, 4){
            rr = r + dr[h]; cc = c + dc[h];
            if(thoaman(rr, cc) && flag[rr][cc] == -1){
                flag[rr][cc] = flag[r][c] + 1;
                que[size++] = mp(rr, cc);
            }
        }
    }
    return inf;
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    while(scanf("%d %d", &m, &n) > 0 && n > 0){
        int run = 0;
        Rep(i, n) {
            cin >> s[i];

            Rep(j, m){
                if(s[i][j] == 'o') P = mp(i, j);
                else if(s[i][j] == '*') A[run++] = mp(i, j);
            }

        }
        Rep(i, run) d[i] = bfs(P, A[i]);
        Rep(i, run) Rep(j, run) if(i != j) a[i][j] = bfs(A[i], A[j]);
       // cout << run << endl;
        ms(f, 0x3f);
        int res = inf;
        For(i, 1, (1 << run) - 1) Rep(j, run) if(getbit(i, j)){
            if(cntbit(i) == 1){
                f[i][j] = d[j];
                continue;
            }
            Rep(k, run) if(getbit(i, k)){
                f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);
            }
            if(i == (1 << run) - 1) res = min(res, f[i][j]);
        }
        if(res >= inf) res = -1;
        cout << res << endl;
    }

   // cout << clock() << endl;
    return 0;
}

Code mẫu của ll931110

Program MCLEAN;
        Const
                input  = '';
                output = '';
                  maxn = 20;
                  maxd = 11;
                  maxv = 20000;
        Type
                rec = record
                  x,y: integer;
                end;
        Var
                fi,fo: text;
                check: array[0..maxn + 1,0..maxn + 1] of boolean;
                 free: array[0..maxn + 1,0..maxn + 1] of boolean;
                    c: array[1..maxn,1..maxn] of char;
                    d: array[0..maxn + 1,0..maxn + 1] of integer;
                dx,dy: array[1..4] of integer;
                   st: array[1..15] of rec;
                queue: array[1..maxn * maxn] of rec;
                    a: array[1..maxd,1..maxd] of integer;
                    F: array[0..2500,1..maxd] of integer;
                    n: integer;
                 mark: integer;
                  w,h: integer;

Procedure openfile;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Assign(fo, output);
                        Rewrite(fo);

                dx[1]:= -1;             dy[1]:= 0;
                dx[2]:= 0;              dy[2]:= 1;
                dx[3]:= 1;              dy[3]:= 0;
                dx[4]:= 0;              dy[4]:= -1;
          End;

Procedure init;
          Var
                i,j: integer;
                 ch: char;
          Begin
                Fillchar(check, sizeof(check), false);
                n:= 1;
                For i:= 1 to h do
                  Begin
                    For j:= 1 to w do
                      Begin
                        Read(fi, c[i,j]);
                        If c[i,j] <> 'x' then
                          Begin
                            check[i,j]:= true;
                            If c[i,j] = 'o' then
                              Begin
                                st[1].x:= i;
                                st[1].y:= j;
                              End
                            else if c[i,j] = '*' then
                              Begin
                                inc(n);
                                st[n].x:= i;
                                st[n].y:= j;
                              End;
                          End;
                    End;
                  Readln(fi);
                End;
          End;

Procedure BFS(i: integer);
          Var
                u,v,u1,v1,k,p: integer;
                   front,rear: integer;
          Begin
                free:= check;
                a[i,i]:= 0;
                mark:= n - 1;

                front:= 1;
                rear:= 1;

                queue[1].x:= st[i].x;
                queue[1].y:= st[i].y;
                free[st[i].x,st[i].y]:= false;

                Fillchar(d, sizeof(d), 0);
                Repeat
                  u:= queue[front].x;
                  v:= queue[front].y;
                  inc(front);

                  For k:= 1 to 4 do
                    Begin
                      u1:= u + dx[k];
                      v1:= v + dy[k];

                      If free[u1,v1] and (d[u1,v1] = 0) then
                        Begin
                          inc(rear);
                          queue[rear].x:= u1;
                          queue[rear].y:= v1;
                          d[u1,v1]:= d[u,v] + 1;
                          free[u1,v1]:= false;

                          If c[u1,v1] = 'o' then
                            Begin
                                dec(mark);
                                a[i,1]:= d[u1,v1];
                            End
                          else if c[u1,v1] = '*' then
                            Begin
                              dec(mark);
                              For p:= 2 to n do
                                if (u1 = st[p].x) and (v1 = st[p].y)
                                        then a[i,p]:= d[u1,v1];
                            End;
                       End;
                  End;

                  if mark = 0 then break;
                Until front > rear;
          End;

Procedure optimize;
          Var
                  i,j,k,t: integer;
                      tmp: integer;
                      min: integer;
          Begin
                For i:= 1 to n do
                  Begin
                        BFS(i);
                        If mark <> 0 then
                          Begin
                                Writeln(fo, -1);
                                exit;
                          End;
                  End;

                For i:= 0 to 1 shl n - 1 do
                  For j:= 1 to n do F[i,j]:= maxv;

                F[1,1]:= 0;
                For i:= 2 to 1 shl n - 1 do
                  For j:= 1 to n do
                    if (i and (1 shl (j - 1))) = (1 shl (j - 1)) then
                      Begin
                        t:= i - 1 shl (j - 1);
                        For k:= 1 to n do
                          if (t and (1 shl (k - 1))) = (1 shl (k - 1)) then
                            Begin
                              tmp:= F[t,k] + a[k,j];
                              If F[i,j] > tmp then F[i,j]:= tmp;
                            End;
                      End;

                min:= maxv;
                For i:= 2 to n do if min > F[1 shl n - 1,i]
                                then min:= F[1 shl n - 1,i];
                Writeln(fo, min);
          End;

Procedure closefile;
          Begin
                Close(fo);
                Close(fi);
          End;

Begin
        openfile;

        Repeat
                Readln(fi, w, h);
                If (w <> 0) or (h <> 0) then
                        Begin
                          init;
                          optimize;
                        End;
        Until (w = 0) and (h = 0);

        closefile;
End.