1 /**************************************************************  2     Problem: 2595  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:160 ms  7     Memory:4444 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <queue> 12 #include <utility> 13   14 #define P Point 15 using namespace std; 16 const int N = 15; 17 const int maxS = 1024; 18 const int inf = 1e9; 19 const int dx[4] = {0, 0, 1, -1}; 20 const int dy[4] = {1, -1, 0, 0}; 21   22 int n, m, K; 23 int a[N][N], bin[N]; 24 int f[N][N][maxS]; 25 bool inq[N][N], used[N][N]; 26   27 struct Point { 28     int x, y; 29     P() {} 30     P(int _x, int _y) : x(_x), y(_y) {} 31 }; 32 queue<P> q; 33   34 struct Path { 35     int x, y, s; 36     Path() {} 37     Path(int _f, int _s, int _t) : x(_f), y(_s), s(_t) {} 38 } path[N][N][maxS]; 39   40 inline int read() { 41     int x = 0; 42     char ch = getchar(); 43     while (ch < ‘0‘ || ‘9‘ < ch) 44         ch = getchar(); 45     while (‘0‘ <= ch && ch <= ‘9‘) { 46         x = x * 10 + ch - ‘0‘; 47         ch = getchar(); 48     } 49     return x; 50 } 51   52 void spfa(int S) { 53     int k, x, y, X, Y; 54     while (!q.empty()) { 55         inq[x = q.front().x][y = q.front().y] = 0, q.pop(); 56         for (k = 0; k < 4; ++k) { 57             X = x + dx[k], Y = y + dy[k]; 58             if (x < 1 || y < 1 || x > n || y > m) continue; 59             if (f[X][Y][S] > f[x][y][S] + a[X][Y]) { 60                 f[X][Y][S] = f[x][y][S] + a[X][Y]; 61                 path[X][Y][S] = Path(x, y, S); 62                 if (!inq[X][Y]) 63                     q.push(P(X, Y)), inq[X][Y] = 1; 64             } 65         } 66     } 67 } 68   69 #define t path[x][y][S] 70 void dfs(int x, int y, int S) { 71     if (x > inf || !path[x][y][S].s) return; 72     used[x][y] = 1; 73     dfs(t.x, t.y, t.s); 74     if (t.x == x && t.y == y) dfs(x, y, S ^ t.s); 75 } 76 #undef t 77   78 void read_in() { 79     int i, j; 80     n = read(), m = read(); 81     for (i = 1; i <= n; ++i) 82         for (j = 1; j <= m; ++j) 83             if (!(a[i][j] = read())) ++K; 84     for (i = bin[0] = 1; i <= K; ++i) 85         bin[i] = bin[i - 1] << 1; 86 } 87   88 void pre_work() { 89     int i, j, k; 90     for (i = 1; i <= n; ++i) 91         for (j = 1; j <= m; ++j) 92             for (k = 0; k < bin[K]; ++k) 93                 f[i][j][k] = path[i][j][k].x = inf; 94     for (i = 1, K = 0; i <= n; ++i) 95         for (j = 1; j <= m; ++j) 96             if (!a[i][j]) 97                 f[i][j][bin[K++]] = 0; 98 } 99  100 void work() {101     int i, j, S, s, tmp;102     for (S = 1; S < bin[K]; spfa(S++))103         for (i = 1; i <= n; ++i)104             for (j = 1; j <= m; ++j) {105                 for (s = S & (S - 1); s; s = S & (s - 1))106                     if ((tmp = f[i][j][s] + f[i][j][S ^ s] - a[i][j]) < f[i][j][S]) {107                         f[i][j][S] = tmp;108                         path[i][j][S] = Path(i, j, s);109                     }110                 if (f[i][j][S] != inf) {111                     q.push(P(i, j)), inq[i][j] = 1;112                 }113             }114 }115  116 void get_ans1() {117     int i, j;118     for (i = 1; i <= n; ++i)119         for (j = 1; j <= m; ++j) if (!a[i][j]) {120             dfs(i, j, bin[K] - 1);121             printf("%d\n", f[i][j][bin[K] - 1]);122             return;123         }124 }125  126 void get_ans2() {127     int i, j;128     for (i = 1; i <= n; ++i, putchar(‘\n‘))129         for (j = 1; j <= m; ++j)130             if (!a[i][j]) putchar(‘x‘); else131             if (used[i][j]) putchar(‘o‘); else132             putchar(‘_‘);133  134 }135  136 int main() {137     read_in();138     pre_work();139     work();140     get_ans1();141     get_ans2();142     return 0;143 }