Untitled

#include<iostream>

using namespace std;

int N, M, viTri, rowRobot, colRobot, cntVetBan, duLieu[25][25], visited[500];
char map[25][25];
int Qx[5000], Qy[5000], front, rear, vs[25][25], step[25][25];
int dirX[4] = {0, -1, 0, 1};
int dirY[4] = {-1, 0, 1, 0};
int MAXX = 10000000, MIN;

bool outOfBoard(int X, int Y) {
    if (X < 0 || X >= N) return true;
    if (Y < 0 || Y >= M) return true;
    return false;
}

void BFS(int vtX, int vtY, int vt) {

    for (int i = 0; i < N; i++) {
        for (int j = 0 ; j < M; j++) {
            vs[i][j] = 0;
            step[i][j] = MAXX;
        }
    }

    vs[vtX][vtY] = 1;
    step[vtX][vtY] = 0;
    front = 0;
    rear = 0;
    Qx[rear] = vtX;
    Qy[rear] = vtY;
    rear++;

    while (front < rear) {
        int xx = Qx[front];
        int yy = Qy[front];
        front++;
        for (int i = 0; i < 4; i++) {
            int xn = xx + dirX[i];
            int yn = yy + dirY[i];
            if (!outOfBoard(xn, yn) && vs[xn][yn] == 0 && map[xn][yn] != 'x') {
                vs[xn][yn] = 1;
                step[xn][yn] = step[xx][yy] + 1;
                Qx[rear] = xn;
                Qy[rear] = yn;
                rear++;
            }
        }
    }

    int index = 1;
    for (int i = 0 ; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i != vtX || j != vtY) {
                if (map[i][j] == '*') {
                    if (index == vt) {
                        index++;
                    }
                    duLieu[index][vt] = step[i][j];
                    duLieu[vt][index] = step[i][j];
                    index++;
                }
            }
        }
    }
}

void backTrack(int row, int numOfSelection, int sum) {
    if (numOfSelection >= cntVetBan - 1) {
        if (MIN > sum) {
            MIN = sum;
        }
        return;
    }

    for (int i = 0 ; i < cntVetBan; i++) {
        if (duLieu[row][i] != 0 && visited[i] == 0) {
            visited[i] = 1;
            backTrack(i, numOfSelection + 1, sum + duLieu[row][i]);
            visited[i] = 0;
        }
    }
}


int main() {
    //freopen("input.txt", "r", stdin);
    while (true) {
        cin >> M >> N;
        if (N == 0 && M == 0) {
            break;
        }
        viTri = 1;
        cntVetBan = 1;
        MIN = MAXX;
        for (int i = 0 ; i < N; i++) {
            for (int j = 0 ; j < M; j++) {
                cin>> map[i][j];
                duLieu[i][j] = 0;
                if (map[i][j] == 'o') {
                    rowRobot = i;
                    colRobot = j;
                }
            }
        }
        
        BFS(rowRobot, colRobot, 0);
        for (int i = 0 ; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == '*') {
                    cntVetBan++;
                    BFS(i, j, viTri);
                    viTri++;
                }
            }
        }
        for (int i = 0 ; i < cntVetBan; i++) {
            visited[i] = 0;
        }
        visited[0] = 1;
        backTrack(0, 0, 0);
        if (MIN == MAXX) {
            cout << "-1" << endl;
        } else {
            cout << MIN << endl;
        }
    }
    return 0;
}