第一行有两个整数，N和 M，描述方块的数目。 
接下来 N行， 每行有 M 个非负整数， 如果该整数为 0， 则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。 相邻的整数用 （若干个） 空格隔开，
行首行末也可能有多余的空格。

由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。 
接下来 N行，每行M 个字符，描述方案中相应方块的情况： 
z  ‘_’（下划线）表示该方块没有安排志愿者； 
z  ‘o’（小写英文字母o）表示该方块安排了志愿者； 
z  ‘x’（小写英文字母x）表示该方块是一个景点； 
注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不
一致（任何一行中，多余的空格都不允许出现） ，都可能导致该测试点不得分。

 对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内

Ljcc930提供SPJ

  1 /*by SilverN*/  2 #include<iostream>  3 #include<algorithm>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<queue>  8 using namespace std;  9 const int INF=0x3f3f3f3f; 10 const int mx[5]={0,1,0,-1,0}; 11 const int my[5]={0,0,1,0,-1}; 12 int read(){ 13     int x=0,f=1;char ch=getchar(); 14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 16     return x*f; 17 } 18 int mp[15][15]; 19 int n,m,k; 20 int id[15]; 21 int f[15][15][1100]; 22 struct pt{ 23     int x,y,w; 24 }p[15][15][1100]; 25 queue<pair<int,int> >q; 26 bool vis[30][30]; 27 void SPFA(int s){ 28     while(!q.empty()){ 29         int x=q.front().first; 30         int y=q.front().second; 31         q.pop(); 32         vis[x][y]=0; 33         for(int k=1;k<=4;k++){ 34             int nx=x+mx[k],ny=y+my[k]; 35             if(nx<1 || nx>n || ny<1 || ny>m)continue; 36             if(f[nx][ny][s]>f[x][y][s]+mp[nx][ny]){ 37                 f[nx][ny][s]=f[x][y][s]+mp[nx][ny]; 38                 p[nx][ny][s]=(pt){x,y,s}; 39                 if(!vis[nx][ny]){ 40                     q.push(make_pair(nx,ny)); 41                     vis[nx][ny]=1; 42                 } 43             } 44         } 45     } 46     return; 47 } 48 void DFS(int x,int y,int s){//标记路径  49     if(x>=INF || !p[x][y][s].w)return; 50     vis[x][y]=1; 51     DFS(p[x][y][s].x,p[x][y][s].y,p[x][y][s].w); 52     if(p[x][y][s].x==x && p[x][y][s].y==y)DFS(p[x][y][s].x,p[x][y][s].y,s-p[x][y][s].w); 53     return; 54 } 55 void Print(){ 56     for(int i=1;i<=n;i++){ 57         for(int j=1;j<=m;j++){ 58             if(!mp[i][j])printf("x"); 59             else if(!vis[i][j])printf("_"); 60             else printf("o"); 61         } 62         printf("\n"); 63     } 64     return; 65 } 66 int main(){ 67     int i,j; 68     n=read();m=read();k=0; 69     for(i=1;i<=n;i++) 70         for(j=1;j<=m;j++){ 71             mp[i][j]=read(); 72             if(!mp[i][j])k++; 73         } 74     // 75     memset(f,0x3f,sizeof f); 76     for(i=1;i<=k;i++)id[i]=1<<(i-1); 77     int ed=(1<<k)-1; 78     for(i=1;i<=n;i++) 79         for(j=1;j<=m;j++) 80             for(int c=0;c<=ed;c++) 81                 p[i][j][c].x=INF; 82     //init 83     k=0; 84     for(i=1;i<=n;i++) 85         for(j=1;j<=m;j++) 86             if(!mp[i][j]){ 87                 f[i][j][id[++k]]=0; 88             } 89     for(int s=1;s<=ed;s++){ 90         for(i=1;i<=n;i++) 91          for(j=1;j<=m;j++){ 92              for(int c=(s-1)&s;c;c=(c-1)&s){ 93                  if(f[i][j][s]>f[i][j][c]+f[i][j][s-c]-mp[i][j]){ 94                      f[i][j][s]=f[i][j][c]+f[i][j][s-c]-mp[i][j]; 95                      p[i][j][s]=(pt){i,j,c}; 96                  } 97              } 98              if(f[i][j][s]<INF){ 99                  q.push(make_pair(i,j));100                  vis[i][j]=1;101             }102          }103         SPFA(s);104     }105     memset(vis,0,sizeof vis);106     while(!q.empty())q.pop();107     for(i=n;i;i--)108         for(j=m;j;j--){109             if(!mp[i][j]){110                 DFS(i,j,ed);111                 printf("%d\n",f[i][j][ed]);112                 Print();113                 return 0;114             }115         }116     return 0;117 }