Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 11

int to(int x,int y){return (x - 1) * m + y;}

int a[MAXN * MAXN],tot = 0;

int f[MAXN * MAXN][1 << MAXN];

struct pre

{

    int id,sta;

}p[MAXN * MAXN][1 << MAXN];

int mx[5] = {0,0,0,1,-1};

int my[5] = {0,1,-1,0,0};

struct edge

{

    int to,nxt,v;

}e[MAXN * MAXN * 4 * 2];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b,int c)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

queue<int> q;

bool v[MAXN * MAXN];

void SPFA(int sta)

{

    while(!q.empty())

    {

        int k = q.front();q.pop();

        v[k] = false;

        for(int i = lin[k];i != 0;i = e[i].nxt)

        {

            if(f[e[i].to][sta] > f[k][sta] + e[i].v)

            {

                f[e[i].to][sta] = f[k][sta] + e[i].v;

                p[e[i].to][sta] = (pre){k,sta};

                if(!v[e[i].to])

                {

                    v[e[i].to] = true;

                    q.push(e[i].to);

                }

            }

        }

    }

    return;

}

bool vis[MAXN * MAXN];

void dfs(int k,int sta)

{

    vis[k] = true;

    if(k == 0)return;

    dfs(p[k][sta].id,p[k][sta].sta);

    if(k == p[k][sta].id)dfs(p[k][sta].id,sta - p[k][sta].sta);

    return;

}

int main()

{

    scanf("%d%d",&n,&m);

    memset(f,0x3f,sizeof(f));

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= m;++j)

        {

            scanf("%d",&a[to(i,j)]);

            if(a[to(i,j)] == 0)

            {

                ++tot;

                f[to(i,j)][1 << (tot - 1)] = 0;

            }

        }

    }

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= m;++j)

        {

            for(int k = 1;k <= 4;++k)

            {

                int nx = i + mx[k],ny = j + my[k];

                if(nx < 1 || nx > n || ny < 1 || ny > m)continue;

                add(to(i,j),to(nx,ny),a[to(nx,ny)]);

            }

        }

    }

    int limit = (1 << tot) - 1;

    for(int sta = 0;sta <= limit;++sta)

    {

        for(int i = 1;i <= n * m;++i)

        {

            for(int s = sta;s != 0;s = (s - 1) & sta)

            {

                if(f[i][sta] > f[i][sta - s] + f[i][s] - a[i])

                {

                    f[i][sta] = f[i][sta - s] + f[i][s] - a[i];

                    p[i][sta] = (pre){i,s};

                }

            }

            if(f[i][sta] < 0x3f3f3f3f)

            {

                q.push(i);

                v[i] = true;

            }

        }

        SPFA(sta);

    }

    int ansx,ansy;

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= m;++j)

        {

            if(a[to(i,j)] == 0)

            {

                ansx = i;ansy = j;

                break;

            }

        }

    }

    cout << f[to(ansx,ansy)][limit] << endl;

    dfs(to(ansx,ansy),limit);

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= m;++j)

        {

            if(a[to(i,j)] == 0)putchar('x');

            else if(vis[to(i,j)])putchar('o');

            else putchar('_');

        }

        puts("");

    }

    return 0;

}