4991.cpp

#include <queue>
#include <tuple>
#include <deque>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int mat[20][20];
int dist[12][20][20];

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	while (true) {
		int n, m;
		cin >> m >> n;
		if (n == 0 && m == 0) break;

		deque<pair<int, int>> trash;
		for (int i = 0; i < n; i++) {
			string s;
			cin >> s;
			for (int j = 0; j < m; j++) {
				if (s[j] == '*') {
					mat[i][j] = 1;
					trash.push_back(make_pair(i, j));
				}
				else if (s[j] == 'o') {
					mat[i][j] = 1;
					trash.push_front(make_pair(i, j));
				}
				else if (s[j] == 'x') {
					mat[i][j] = -1;
				}
				else if (s[j] == '.') {
					mat[i][j] = 0;
				}
			}
		}
		
		memset(dist, -1, sizeof(dist));
		for (int i = 0; i < trash.size(); i++) {
			int tshx = trash[i].first;
			int tshy = trash[i].second;
			
			queue<pair<int, int>> q;
			q.push(make_pair(tshx, tshy));
			dist[i][tshx][tshy] = 0;

			while (!q.empty()) {
				int x, y;
				tie(x, y) = q.front();
				q.pop();

				for (int k = 0; k < 4; k++) {
					int tx = x + dx[k];
					int ty = y + dy[k];
					if (tx < 0 || ty < 0 || tx > n - 1 || ty > m - 1 || mat[tx][ty] == -1 || dist[i][tx][ty] != -1) continue;
					dist[i][tx][ty] = dist[i][x][y] + 1;
					q.push(make_pair(tx, ty));
				}
			}
		}
		vector<int> idx(trash.size());
		for (int i = 0; i < trash.size(); i++) {
			idx[i] = i;
		}
	
		int ans = -1;
		do {
			int tsum = 0;
			int st = 0;
			bool ok = true;
			for (int i = 1; i < idx.size(); i++) {
				if (dist[st][trash[idx[i]].first][trash[idx[i]].second] == -1) {
					ok = false;
					break;
				}
				tsum += dist[st][trash[idx[i]].first][trash[idx[i]].second];
				st = idx[i];
			}
			if (ok && (ans == -1 || ans > tsum)) {
				ans = tsum;
			}
		} while (next_permutation(idx.begin() + 1, idx.end()));

		cout << ans << '\n';
	}

	return 0;
}