PKU 1481 The Die Is Cast
http://poj.org/problem?id=1481
賽は投げられた。
サイコロの面を読み取って、目の数を答えろというような問題。
簡単な問題だと思ったのに、目の探索の後、面の探索用にq1に放り込むのを忘れて何回かWAをもらいました。
番号はそんなに新しくないのに提出の数が少ないのが個人的には謎。
2回BFSしているので、冗長になってしまったのがちょっと残念。
string in[50]; int w,h; main(){ int th=0; while(cin>>w>>h,w|h){ vector<int> ans; rep(i,h)cin>>in[i]; printf("Throw %d\n",++th); rep(i,h){ rep(j,w){ if(in[i][j]=='.')continue; int me=0; queue<PI> q1; q1.push(mp(i,j)); while(!q1.empty()){ int x1=q1.front().F,y1=q1.front().S; q1.pop(); if(in[x1][y1]=='*'){ in[x1][y1]='.'; rep(i,4){ int nx=x1+dx[i],ny=y1+dy[i]; if(0>nx || nx>=h || 0>ny || ny>=w || in[nx][ny]=='.')continue; q1.push(mp(nx,ny)); } }else if(in[x1][y1]=='X'){ q1.push(mp(x1,y1)); ++me; queue<PI> q; q.push(mp(x1,y1)); while(!q.empty()){ int cx=q.front().F,cy=q.front().S; q.pop(); if(in[cx][cy]!='X')continue; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(0>nx || nx>=h || 0>ny || ny>=w || in[nx][ny]!='X')continue; q.push(mp(nx,ny)); } in[cx][cy]='*'; } } } ans.pb(me); } } sort(ALL(ans)); rep(i,SZ(ans))printf("%d%c",ans[i],i+1==SZ(ans)?'\n':' '); cout<<endl; } }