thanhthuy4u's blog

By thanhthuy4u, history, 7 years ago, In English

http://mirror.codeforces.com/contest/723/submission/29104913 D. Lakes in Berland.

include

include

include

include

include<string.h>

using namespace std;

define max 100

char a[max][max]; int n,m,dem=0,flag=0; bool visited[max][max]; int dx[] = {0,0,-1,1}; int dy[] = {-1,1,0,0}; int option(int x, int y) { return x>y; } struct POINT { int x,y; }; int DFS(POINT src) { dem=0; stacks; visited[src.x][src.y]=true; s.push(src); while(!s.empty()) { POINT w; src=s.top(); s.pop(); for(int i=0;i<4;i++) { int x,y; x=src.x+dx[i]; y=src.y+dy[i]; if(visited[x][y]==false&&a[x][y]=='.'&&x>=0&&x<n&&y>=0&&y<m) { if(flag==1) { a[x][y]='*'; } visited[x][y]=true; w.x=x;w.y=y; s.push(w); dem++; } } } return dem; }

int main() { //freopen("input.txt","rt",stdin); int k,d=0,oo[max],ooo[max],dd,ans=0,kq=0;; POINT p; POINT o[max]; cin>>n>>m>>k; for(int i=0;i<n;i++) for(int j=0;j<m;j++) visited[i][j]=false; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>a[i][j]; } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(visited[i][j]==false&&a[i][j]=='.'&&(i==0||i==n-1||j==0||j==m-1)) { p.x=i;p.y=j; DFS(p); } } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]=='.'&&visited[i][j]==false) { p.x=i;p.y=j; DFS(p); oo[d]=dem+1; ooo[d]=dem+1; o[d++]=p; } } } flag=1; dd=d; sort(ooo,ooo+max,option); for(int i=0;i<n;i++) for(int j=0;j<m;j++) visited[i][j]=false; for(int i=dd-1;i>=0;i--) { for(int j=0;j<d;j++) { if(oo[j]==ooo[i]) { a[o[j].x][o[j].y]='*'; kq++; kq+=DFS(o[j]); ans++; oo[i]=0; break; } } if(d-k==ans) { cout<<kq<<"\n"; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cout<<a[i][j]; } cout<<"\n"; } break; } } return 0; }

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it