fork download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. int i,j,k,n,m,a[128][128],z,x,y,t,s,l,b,A,v[128][128],
  4. f[256][128],g[256][128],X[]={0,1,0,-1},Y[]={1,0,-1,0};
  5. char u[128][128];
  6. char p[]="0123456789abcdefghijklmnopqrstuvwxyz";
  7. void dfs(int x,int y,int d){
  8. for(int i=0;i<4;++i){
  9. t=x+X[i];s=y+Y[i];
  10. if(t>=0&&s>=0&&t<n&&s<m)
  11. if(d+a[t][s]<f[t*m+s][z]){
  12. f[t*m+s][z]=d+a[t][s];
  13. g[t*m+s][z]=0;
  14. dfs(t,s,d+a[t][s]);
  15. }
  16. }
  17. }
  18. void ff(int x,int y,int z){
  19. u[x][y]='X';
  20. if(g[x*m+y][z]==0){
  21. int r=f[x*m+y][z]-a[x][y];
  22. if(r){
  23. for(int i=0;i<4;++i){
  24. t=x+X[i];s=y+Y[i];
  25. if(t>=0&&s>=0&&t<n&&s<m)
  26. if(f[t*m+s][z]==r){
  27. ff(t,s,z);
  28. break;
  29. }
  30. }
  31. }
  32. }
  33. else
  34. {
  35. int w=g[x*m+y][z];
  36. for(int i=0;i<4;++i){
  37. t=x+X[i];s=y+Y[i];
  38. if(t>=0&&s>=0&&t<n&&s<m)
  39. if(f[t*m+s][w]+f[x*m+y][z^w]==f[x*m+y][z]){
  40. ff(t,s,w);
  41. ff(x,y,z^w);
  42. break;
  43. }
  44. }
  45. }
  46. }
  47. int main(){
  48. scanf("%d%d%d",&n,&m,&k);
  49. for(;i<n;++i){
  50. memset(u[i],'.',m);
  51. for(j=0;j<m;++j)scanf("%d",a[i]+j);
  52. }
  53. memset(f,32,sizeof(f));
  54. memset(v,255,sizeof(v));
  55. for(i=0;i<k;++i){
  56. scanf("%d%d",&x,&y);--x;--y;z=1<<i;
  57. v[x][y]=i;
  58. dfs(x,y,f[x*m+y][z]=a[x][y]);
  59. }
  60. for(z=3;z<(1<<k);++z)if(__builtin_popcount(z)>1)
  61. for(x=z-1;x;x=(x-1)&z){
  62. y=x^z;
  63. for(i=A=0;i<n;++i)for(j=0;j<m;++A,++j)
  64. for(l=0;l<4;++l){
  65. t=i+X[l];s=j+Y[l];
  66. if(t>=0&&s>=0&&t<n&&s<m){
  67. b=t*m+s;
  68. if(f[A][x]+f[b][y]<f[A][z]){
  69. f[A][z]=f[A][x]+f[b][y];
  70. g[A][z]=y;
  71. }
  72. }
  73. }
  74. for(y=16;y--;)
  75. for(i=A=0;i<n;++i)for(j=0;j<m;++A,++j)
  76. for(l=0;l<4;++l){
  77. t=i+X[l];s=j+Y[l];
  78. if(t>=0&&s>=0&&t<n&&s<m)
  79. if(!~v[t][s]){
  80. b=t*m+s;
  81. if(f[A][z]+a[t][s]<f[b][z]){
  82. f[b][z]=f[A][z]+a[t][s];
  83. g[b][z]=0;
  84. }
  85. }
  86. }
  87. }
  88. for(z=(1<<k)-1,i=n*m,j=0;--i;)if(f[i][z]<f[j][z])j=i;
  89. printf("%d\n",f[j][z]);
  90. ff(j/m,j%m,z);
  91. for(i=0;i<n;++i)puts(u[i]);
  92. return 0;
  93. }
Success #stdin #stdout 0s 3092KB
comments (?)
stdin
copy 
3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3
stdout
copy 
9
.X.
.X.
.XX
https://ideone.com/T7suW0
language:
C++ 4.3.2 (gcc-4.3.2)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!