Page 1 of 4

### 657 - The die is cast

Posted: Fri Dec 20, 2002 3:21 pm
I know this problem is tricky floodfill, but I think I'm handling the "tricky" part well (or so I think of course, which explains my WA). Does anyone have any tricky or boundary test cases?

Thanks.

Posted: Sun Dec 22, 2002 6:03 pm
helo
in:
30 15
.....X*X*X*X*X*X***...........
.X......................X.....
...............*.........X....
...X****......****........X...
...*X*.*.....**X***X..........
...*.X......***X**.....XXX....
...*.*X*.....****........X....
...***.X.......*.........X....
..............................
.......X***.............*..***
......******X****.....*X**X*..
..***********......**.*.*.....
.....****X**.......*X**X*.....
........***........*....*.....
........***.********..........
0 0
out:
Throw 1
1 1 1 1 1 2 3 4 5 6

bye

Posted: Mon Apr 21, 2003 11:09 am
Could you help me....
I try to solve this by BrFS algorithm

Posted: Mon Apr 21, 2003 1:24 pm
Can you describe your method, or post your code? Here or PM...

### RTE WHY?

Posted: Mon Feb 09, 2004 8:15 pm
I tried several times and always got RTE
it is so strange
hope some one can help me

Posted: Tue Feb 10, 2004 7:54 am
U only need add one sentence :
[cpp]
visited[x][y]=true;
[/cpp]

Posted: Tue Feb 10, 2004 12:18 pm
I got AC!
How careless i am

but many tks to galois_godel

### 657 The die is cast WA

Posted: Mon Aug 02, 2004 1:43 pm
Hi I'm getting WA for this problem. It works on inputs I got from the official website. My algorithm is to do one flood-fill to mark all non-background pixels with a positive component number, then do a second flood-fill to mark all the dots on the die with a negative component number (negative of original). I cannot see why this gives WA.

I believe there's bad input. They give input where both w and h are less than 5, which is not suppose to happen.

Code: Select all

``````#include <iostream>
#include <algorithm>
using namespace std;

int comp[60][60];
char mp[60][60];
int num_comp;

int w, h;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
bool inbounds( int r, int c )
{
return ( r >= 0 && r < h && c >= 0 && c < w );
}
void flood_fill( int r, int c, int cp )
{
comp[r][c] = cp;
for (int i=0; i<4; i++) {
int nr = r+dr[i];
int nc = c+dc[i];
if ( inbounds(nr,nc) &&
mp[nr][nc] != '.' &&
comp[nr][nc] == 0 ) {
flood_fill( nr, nc, cp );
}
}
}
void flood_dots( int r, int c )
{
comp[r][c] *= -1;
for (int i=0; i<4; i++) {
int nr = r+dr[i];
int nc = c+dc[i];
if ( inbounds(nr,nc) &&
mp[nr][nc] == 'X' &&
comp[nr][nc] > 0 ) {
flood_dots( nr, nc );
}
}
}

int main()
{
int T = 1;
while ( cin >> w >> h && !(w==0&&h==0) ) {
//    if ( w < 5 || h < 5 ) throw;
for (int i=0; i<h; i++) {
for (int j=0; j<w; j++) {
cin >> mp[i][j];
}
}

for (int i=0; i<h; i++) {
for (int j=0; j<w; j++) {
comp[i][j] = 0;
}
}

num_comp = 0;
for (int i=0; i<h; i++) {
for (int j=0; j<w; j++) {
if ( mp[i][j] != '.' && comp[i][j] == 0 ) {
flood_fill(i,j,++num_comp);
}
}
}

int numdots[num_comp+1];
for (int i=1; i<=num_comp; i++)
numdots[i] = 0;
for (int i=0; i<h; i++) {
for (int j=0; j<w; j++) {
if ( mp[i][j] == 'X' && comp[i][j] > 0 ) {
numdots[comp[i][j]]++;
flood_dots( i, j );
}
}
}

sort( numdots+1, numdots+num_comp+1 );
cout << "Throw " << T++ << endl;
for (int i=1; i<=num_comp; i++) {
cout << numdots[i] << " ";
}
cout << endl;
cout << endl;
}
return 0;
}
``````
Thanks in advance for any help.
Frank

Posted: Tue Aug 10, 2004 7:17 am
Dear Frank, try these inputs. The output is generated by my AC program

INPUT :

5 5
XXX*X
XXX*X
.....
X***X
XX***
10 5
..........
..X**.*X..
..........
...*X*X...
..........
10 5
..........
..X....X..
..........
...*X*X...
..........
10 5
..........
..X....X..
..X....X..
..XXXXXX..
..........
10 5
..........
..X*X.....
..*X*.....
..X*X.....
..........
10 5
..........
..X*X.....
..*X**....
..X*X*....
..........
5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX
0 0

OUTPUT:

Throw 1
2 2
Throw 2
1 1 2
Throw 3
1 1 2
Throw 4
1
Throw 5
5
Throw 6
5
Throw 7
1

Posted: Sat Aug 14, 2004 3:02 am
Strange, you posted 6 input cases and there's 7 output??

But I checked manually and my program seems to work for your test input cases...... unfortunate...

Please can anyone help me out here???
Frank

Posted: Sat Aug 14, 2004 5:23 am
I made a mistake here. I forgot to type the first case which gives the output:
2 2

I have corrected my previous post. Sorry for the mistake.

Here are some more cases for you.

INPUT:

10 6
..........
.XXX......
....XXX...
.......XXX
....XXX...
*X*X......
6 6
XXXXX*
.....X
.....X
.....X
.....X
.....X
6 6
XXXXX.
.....X
.....X
.....X
.....X
.....X
6 6
XXXXX.
....*X
.....X
.....X
.....X
.....X
0 0

OUTPUT:

Throw 1:
1 1 1 1 2
Throw 2:
2
Throw 3:
1 1
Throw 4:
2

### 657 The die is cast [WA]

Posted: Fri Sep 29, 2006 8:07 am
Hi
I try many testdata whuch i found in this forum.
but i still cannot find any wrong.

The problem is very easy.But i cannot got AC. T T

Code: Select all

``````#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
char map[51][51];
int w,h;
int sum;
int dfs(int sx,int sy,int fillmode)
{
static int dx[]={1,0,-1,0};
static int dy[]={0,1,0,-1};
int nx,ny;
int i,j,k;
for(i=0;i<4;i++){
nx=dx[i]+sx;
ny=dy[i]+sy;
if( nx>=0 &&ny>=0 && nx<w && ny<h ){
if( fillmode==0 ){
if( map[nx][ny]=='X' ){
map[nx][ny]=0;
sum++;
dfs( nx,ny,1 );
}else if( map[nx][ny]=='*' ){
map[nx][ny]=0;
dfs( nx,ny,0 );
}
}else if( fillmode==1 ){
if( map[nx][ny]=='*' ){
map[nx][ny]=0;
dfs( nx,ny,0 );
}else if( map[nx][ny]=='X' ){
map[nx][ny]=0;
dfs(nx,ny,1);
}
}
}
}
}
int cmp( const void *a,const void *b)
{
return  *(( int *)a) - *(( int *)b);
}
void solve()
{
int i,j,k;
static int ans[60*60];
int ans_count=0;
k=0;
for(i=0;i<h;i++)
for(j=0;j<w;j++){
if( map[j][i]=='*' ){
sum=0;
dfs( j,i,0 );
ans[ans_count++]=sum;
}else if( map[j][i]=='X' ){
sum=1;
map[j][i]=0;
dfs( j,i,1 );
ans[ans_count++]=sum;
}
}
qsort( ans,ans_count,sizeof(int) ,cmp );
for(i=0;i<ans_count;i++){
if( i>0 ) cout<<" ";
cout<<ans[i];
}
cout<<endl;
}
int main()
{
int i,j,k;
char str[100];
int T=0;
while( true ){

cin.getline( str,sizeof(str));
w=atoi(strtok(str," "));
h=atoi(strtok(NULL," "));
if( !w && !h )
break;
for(i=0;i<h;i++){
cin.getline( str,sizeof(str) );
for(j=0;j<w;j++){
map[j][i]=str[j];
}
}
cout << "Throw " << ++T <<endl;
solve();
}

return 0;
}
``````

Posted: Fri Jun 29, 2007 4:25 pm
I have tried all the inputs available in this forum. It gives correct answer for all of them.

Code: Select all

``````#include<stdio.h>
char map[53][53],map_copy[53][53];
int ind,value[2500],flags[53][53],VALUE;
void removeX(int i,int j)
{
map[i][j]='.';
if(map[i-1][j]=='X')
removeX(i-1,j);
if(map[i][j-1]=='X')
removeX(i,j-1);
if(map[i+1][j]=='X')
removeX(i+1,j);
if(map[i][j+1]=='X')
removeX(i,j+1);
}
void mark_all(int i,int j)
{
map_copy[i][j]='.';
flags[i][j]=VALUE;
if(map_copy[i-1][j]=='X'||map_copy[i-1][j]=='*')
mark_all(i-1,j);
if(map_copy[i+1][j]=='X'||map_copy[i+1][j]=='*')
mark_all(i+1,j);
if(map_copy[i-1][j-1]=='*')
mark_all(i-1,j-1);
if(map_copy[i+1][j-1]=='*')
mark_all(i+1,j-1);
if(map_copy[i][j-1]=='X'||map_copy[i][j-1]=='*')
mark_all(i,j-1);
if(map_copy[i-1][j+1]=='*')
mark_all(i-1,j+1);
if(map_copy[i][j+1]=='X'||map_copy[i][j+1]=='*')
mark_all(i,j+1);
if(map_copy[i+1][j+1]=='*')
mark_all(i+1,j+1);
}
int main()
{
int i,j,m,n,count=0,t=0,tc;
while(1)
{
scanf("%d%d",&n,&m);
if(!m&&!n)
break;
for(i=1;i<=m;scanf(" %s",map[i]+1),++i);
for(i=0;i<2500;value[i]=0,++i);
for(i=0;i<=m+1;map[i][0]=map[i][n+1]='.',++i);
for(i=0;i<=n+1;map[0][i]=map[m+1][i]='.',++i);
for(i=0;i<=m+1;++i)
for(j=0;j<=n+1;flags[i][j]=-1,map_copy[i][j]=map[i][j],++j);
for(VALUE=-1,i=1;i<=m;++i)
for(j=1;j<=n;++j)
if(map_copy[i][j]!='.'&&flags[i][j]==-1)
{
++VALUE;
mark_all(i,j);
}
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
if(map[i][j]=='X')
{
++value[flags[i][j]];
removeX(i,j);
}
if(t)
printf("\n");
else
t=1;
printf("Throw %d\n",++count);
++VALUE;
tc=0;
for(i=0;i<VALUE-1;++i)
for(j=0;j<VALUE-1-i;++j)
if(value[j]>value[j+1])
{
value[j]^=value[j+1];
value[j+1]^=value[j];
value[j]^=value[j+1];
}
for(i=0;i<VALUE;++i)
{
if(tc)
printf(" ");
else
tc=1;
printf("%d",value[i]);
}
printf("\n");
for(i=0;i<=100000;++i);
}
return 0;
}``````

### 657 - The die is cast

Posted: Thu Apr 23, 2009 9:35 am
im confused with this prob. can any body explain wht does that mean??

A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ...., ak in S such that a = a1 and b = ak , and ai and ai+1 are connected for 1 <= i < k.

We consider all maximally connected sets consisting solely of non-background pixels to be dice. `Maximally connected' means that you cannot add any other non-background pixels to the set without making it dis-connected. Likewise we consider every maximal connected set of dot pixels to form a dot.

thnks.

### Re: 657 - The die is cast

Posted: Tue Apr 28, 2009 8:04 am