657 - The die is cast

junjieliang · Post by **junjieliang** » 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.

tat tvam asi · Post by **tat tvam asi** » Sun Dec 22, 2002 6:03 pm

helo
... what about this one :
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

D.M. · Post by **D.M.** » Mon Apr 21, 2003 11:09 am

Could you help me....
I try to solve this by BrFS algorithm

junjieliang · Post by **junjieliang** » Mon Apr 21, 2003 1:24 pm

Can you describe your method, or post your code? Here or PM...

sjn · Post by **sjn** » 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

thx in advance

galois_godel · Post by **galois_godel** » Tue Feb 10, 2004 7:54 am

U only need add one sentence :
[cpp]
visited[x][y]=true;
[/cpp]

sjn · Post by **sjn** » Tue Feb 10, 2004 12:18 pm

I got AC!
How careless i am

but many tks to galois_godel

fpmc · Post by **fpmc** » 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

Raiyan Kamal · Post by **Raiyan Kamal** » 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

fpmc · Post by **fpmc** » 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

Raiyan Kamal · Post by **Raiyan Kamal** » 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

hank · Post by **hank** » Fri Sep 29, 2006 8:07 am

Hi
My solution got Wrong Answer.
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;
}

Help me please!

Thanks in advance!

abhiramn · Post by **abhiramn** » Fri Jun 29, 2007 4:25 pm

Please help me.
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;
}

Please help

calicratis19 · Post by **calicratis19** » 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.

calicratis19 · Post by **calicratis19** » Tue Apr 28, 2009 8:04 am

somebody pls reply. pls....

OJ Board