SRM396 div1 medium
めんどくさい。
#include <queue> #include <string> #include <vector> using namespace std; class FixImage { public: int h,w; int image[60][60]; int color() { for(int i=0;i<h;i++) for(int j=0;j<w;j++) if(image[i][j]!=-1) image[i][j]=3000; int c=0; for(int sy=0;sy<h;sy++) for(int sx=0;sx<w;sx++) if(image[sy][sx]==3000) { queue<int> que; que.push(sy*60+sx); while(!que.empty()) { int y=que.front()/60,x=que.front()%60; que.pop(); if(image[y][x]==3000) { image[y][x]=c; if(y<h-1 && image[y+1][x]==3000) que.push((y+1)*60+x); if(0<y && image[y-1][x]==3000) que.push((y-1)*60+x); if(x<w-1 && image[y][x+1]==3000) que.push(y*60+x+1); if(0<w && image[y][x-1]==3000) que.push(y*60+x-1); } } c++; } return c; } void fill(int c) { for(int y=0;y<h;y++) { int left,right; for(left=0;left<w;left++) if(image[y][left]==c) break; for(right=w-1;0<=right;right--) if(image[y][right]==c) break; for(int x=left;x<=right;x++) image[y][x]=c; } for(int x=0;x<w;x++) { int bottom,ceil; for(bottom=0;bottom<h;bottom++) if(image[bottom][x]==c) break; for(ceil=h-1;0<=ceil;ceil--) if(image[ceil][x]==c) break; for(int y=bottom;y<=ceil;y++) image[y][x]=c; } } vector <string> originalImage(vector <string> alteredImage) { h=alteredImage.size(),w=alteredImage[0].size(); for(int i=0;i<h;i++) for(int j=0;j<w;j++) image[i][j]=(alteredImage[i][j]=='.')?-1:3000; for(int time=0;time<50;time++) { int n=color(); for(int i=0;i<=n;i++) fill(i); } for(int i=0;i<h;i++) for(int j=0;j<w;j++) alteredImage[i][j]=(image[i][j]==-1)?'.':'#'; return alteredImage; } };