斯坦纳树的问题模型是：有一个图，要求保留图中最少的边/最小的边权和使得某k个点相互连通。最小生成树是斯坦纳树的一种特殊情况。

我们用f[i]][j][s]表示方格中i,j位置与各个景点之间的联通情况。
如果景点数为3时，111表示全部联通， 101表示第二个景点没有联通。。。
当然第x个景点的 f[i][j][(1<<x)] = 0，其他的情况先初始化为inf。

状态怎么转移？
有两种情况
1.某个状态的子状态（11011->10001）。
2.相邻的位置转移过来的。

子状态的话需要知道一个枚举子状态的技巧：

for(int s = st&(st-1); s; s = st&(s-1))

相邻的状态转移就要用spfa了。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<12;
int Case = 1;
int n, m, cc[12][12], f[12][12][maxn], vis[12][12], res[12][12];
int dr[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
queue<pair<int, int> >Q;
struct node{
	int i, j, s;
}pre[12][12][maxn];

void dfs(int x, int y, int s) {
	if(!pre[x][y][s].s) return;
	res[x][y] = 1;
	dfs(pre[x][y][s].i, pre[x][y][s].j, pre[x][y][s].s);
	if(pre[x][y][s].i == x && pre[x][y][s].j == y)
		dfs(x, y, pre[x][y][s].s^s);
}

void spfa(int s) {
	while(!Q.empty()) {
		int x = Q.front().first, y = Q.front().second;Q.pop();
		vis[x][y] = 0;
		for(int i = 0; i < 4; i++) {
			int nx = x + dr[i][0];
			int ny = y + dr[i][1];
			if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && f[x][y][s] + cc[nx][ny] < f[nx][ny][s]) {
				f[nx][ny][s] = f[x][y][s] + cc[nx][ny];
				pre[nx][ny][s] = node{x, y, s};
				if(!vis[nx][ny]) Q.push(make_pair(nx, ny)), vis[nx][ny] = 1;
			}
		}
	}
}

void solve() {
	int sx, sy;
    scanf("%d%d", &n, &m);
   	memset(f, 0x3f3f, sizeof(f));
    int num = 0;
    for(int i = 1; i <= n; i++) {
    	for(int j = 1; j <= m; j++) {
    		scanf("%d", &cc[i][j]);
    		if(!cc[i][j]) {f[i][j][(1<<(num++))] = 0;sx = i;sy = j;}
    	}
    }
    int mx = 1<<num;
    for(int st = 0; st < mx; st++) {
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= m; j++) {
    			for(int s = st&(st-1); s; s = st&(s-1)) {
    				if(f[i][j][s] + f[i][j][st-s] - cc[i][j] < f[i][j][st]) {
    					f[i][j][st] = f[i][j][s] + f[i][j][st-s] - cc[i][j];
    					pre[i][j][st] = node{i, j, s};
    				}
    			}
    			if(f[i][j][st] < 0x3f3f) Q.push(make_pair(i, j)), vis[i][j] = 1;
    		}
    	}
    	spfa(st);
    }
   	printf("%d\n", f[sx][sy][(1<<num)-1]);
   	dfs(sx, sy, (1<<num)-1);
   	for(int i = 1; i <= n; i++) {
   		for(int j = 1; j <= m; j++) {
   			if(cc[i][j] == 0) printf("x");
   			else if(res[i][j]) printf("o");
   			else printf("_");
   		}
   		printf("\n");
   	}
    return;
}

int main() {
    while(Case--) {
        solve();
    }
    return 0;
}