神之 UKE

#include<bits/stdc++.h>

using namespace std;

const int N = 12;
const int M = (1 << 10) + 5;
const int INF = 5e7;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct Node{
  int x, y;
  long long cnt;
  bool operator < (const Node &b) const{
    return cnt > b.cnt;
  }
};

struct node{
  int x, y, state;
}pre[N][N][M], p[N][N];

bool vis[N][N];
long long dist[N][N];
priority_queue<Node> heap;
int n, m, tot, a[N][N], id[N][N], dp[N][N][M], ans[N][N];
//(n - 1) * (i - 1) + j - 1

bool Record(int x, int y, long long cnt){
  if(cnt >= dist[x][y]) return 0;
  dist[x][y] = cnt, heap.push({x, y, cnt});
  return 1;
}

void dfs(int x, int y, int state){
  if(!x) return ;
  //cout << x << ' ' << y << ' ' << state << ' ' << dp[x][y][state] << '\n';
  ans[x][y] = 1;
  dfs(pre[x][y][state].x, pre[x][y][state].y, pre[x][y][state].state);
  if(x == pre[x][y][state].x && y == pre[x][y][state].y){
    dfs(pre[x][y][state].x, pre[x][y][state].y, state - pre[x][y][state].state);
  }
}

void print(){
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(a[i][j] == 0){
        cout << 'x';
      }
      else if(ans[i][j] == 1){
        cout << 'o';
      }
      else{
        cout << '-';
      }
    }
    cout << '\n';
  }
}

int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
      if(a[i][j] == 0){
        id[i][j] = tot++;
      }
    }
  }
  if(tot == 0){
    cout << 0 << '\n';
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        cout << '-';
      }
      cout << '\n';
    }
    return 0;
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      for(int k = 0; k < (1 << tot); k++){
        dp[i][j][k] = INF;
      }
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      dp[i][j][0] = 0;
      if(a[i][j] == 0){
        dp[i][j][(1 << id[i][j])] = 0;
      }
      else{
        dp[i][j][0] = a[i][j];
      }
    }
  }
  for(int k = 0; k < (1 << tot); k++){
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        for(int s = k; s; s = (s - 1) & k){
          int num = dp[i][j][s] + dp[i][j][k - s] - a[i][j];
          if(num < dp[i][j][k]){
            dp[i][j][k] = num;
            pre[i][j][k] = {i, j, s};
          }
        }
      }
    }
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        vis[i][j] = 0, dist[i][j] = INF + 5;
      }
    }
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        p[i][j] = {0, 0, 0};
        if(dp[i][j][k] < INF){
          Record(i, j, dp[i][j][k]);
        }
      }
    }
    while(!heap.empty()){
      Node q = heap.top();
      heap.pop();
      if(vis[q.x][q.y]) continue;
      vis[q.x][q.y] = 1;
      for(int dir = 0; dir < 4; dir++){
        int nx = q.x + dx[dir], ny = q.y + dy[dir];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m){
          if(Record(nx, ny, q.cnt + a[nx][ny])){
            p[nx][ny] = {q.x, q.y, k};
          }
        }
      }
    }
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        if(dp[i][j][k] > dist[i][j]){
          pre[i][j][k] = p[i][j];
        }
        dp[i][j][k] = dist[i][j];
        //cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k] << '\n';
      }
    }
  }
  int ans = INF;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      ans = min(ans, dp[i][j][(1 << tot) - 1]);
    }
  }
  cout << ans << '\n';
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(ans == dp[i][j][(1 << tot) - 1]){
        dfs(i, j, (1 << tot) - 1);
        print();
        return 0;
      }
    }
  }
  return 0;
}