Advertisement
jeff69

Untitled

Oct 3rd, 2016
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. int n,m,k;
  6. char ch[55][55];
  7. bool vis[55][55];
  8. bool check(int x,int y)
  9. {
  10. return x>=0&&y>=0&&y<m&&x<n;
  11. }
  12. bool ocean(int x,int y)
  13. {
  14. if(x==0)return 1;
  15. if(y==0)return 1;
  16. if(x==n-1)return 1;
  17. if(y==m-1)return 1;
  18. return 0;
  19. }
  20. int dx[4]={1,0,-1,0};
  21. int dy[4]={0,1,0,-1};
  22. int dfs(int x,int y)
  23. {
  24. if(vis[x][y])return 0;
  25. if(ocean(x,y))return -1e5;
  26.  
  27. vis[x][y]=1;
  28. int ans=1;
  29. for(int i=0;i<4;i++)
  30. {
  31. int nx,ny;
  32. nx=x+dx[i];
  33. ny=y+dy[i];
  34.  
  35. if(!check(nx,ny))continue;
  36.  
  37. // cout<<nx<<' '<<ny<<endl;
  38. if(ch[nx][ny]=='*')continue;
  39.  
  40. ans+=dfs(nx,ny);
  41. }
  42. return ans;
  43.  
  44. }
  45. void dff(int x,int y)
  46. {
  47.  
  48. ch[x][y]='*';
  49. for(int i=0;i<4;i++)
  50. {
  51. int nx,ny;
  52. nx=x+dx[i];
  53. ny=y+dy[i];
  54. if(!check(nx,ny))continue;
  55.  
  56. // cout<<nx<<' '<<ny<<endl;
  57. if(ch[nx][ny]=='*')continue;
  58. dff(nx,ny);
  59.  
  60. }
  61.  
  62.  
  63. }
  64. vector<pair<int,pair<int,int>>> vr;
  65. int main()
  66. {
  67. // cout<<vis[1][2];;
  68. cin>>n>>m>>k;
  69. for(int i=0;i<n;i++)
  70. for(int c=0;c<m;c++)
  71. cin>>ch[i][c];
  72. int po=0;
  73. for(int i=0;i<n;i++)
  74. for(int c=0;c<m;c++)
  75. {
  76. if(vis[i][c])continue;
  77. if(ch[i][c]!='.')continue;
  78. // cout<<i<<' '<<c<<endl;
  79. int g=dfs(i,c);
  80. if(g<=0)continue;
  81. po++;
  82. vr.push_back({g,{i,c}});
  83. }
  84. sort(vr.rbegin(),vr.rend());
  85. int ret=0;
  86. k=po-k;
  87. while(k--)
  88. {
  89. int g=vr.back().first;
  90. ret+=g;
  91. int ux=vr.back().second.first;
  92. int uy=vr.back().second.second;
  93. vr.pop_back();
  94. dff(ux,uy);
  95.  
  96. }
  97. cout<<ret<<endl;
  98. for(int i=0;i<n;i++){
  99. for(int c=0;c<m;c++)
  100. cout<<ch[i][c];
  101. cout<<endl;
  102. }
  103.  
  104. return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement