0118-Property Distribution
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0118
0156のソースの大半を流用。hとwが0156と逆なことに気づかず1回Wrong Answerを食らってしまった。
問題概略
区間わけ
考え方
一度訪れたところをペイント的に塗りつぶす。
すでに塗りつぶされたところはカウントしない。
計算量はO(WxH)
実装(C++/インクルード省略)
using namespace std; unsigned char MAP[102][102]; struct point{int x;int y;}; int n,m,t; void paint(point p,char d){ int x=p.x,y=p.y; int k=MAP[x][y]; std::stack<point> s; s.push(p); while(s.empty()==false){ p=s.top();s.pop(); x=p.x;y=p.y; if(MAP[x][y]==k){ p.x=x+1,p.y=y;s.push(p); p.x=x-1,p.y=y;s.push(p); p.x=x,p.y=y+1;s.push(p); p.x=x,p.y=y-1;s.push(p); MAP[x][y]=d; } } } void paint2(int x,int y,char d){ point p; p.x=x;p.y=y; paint(p,d); } int main() { for(;;){ scanf("%d%d\n",&n,&m); if(n==0)return 0; if(m==0)return 0; memset(MAP,255,102*102); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ t=getchar();if(t==EOF)return 0; if(t=='#')MAP[j][i]=1;else if(t=='*')MAP[j][i]=2;else if(t=='@')MAP[j][i]=3; } t=getchar(); } t=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(MAP[j][i]!=0){ t++;paint2(j,i,0); } } } printf("%d\n",t); } return 0; }