OJ Board

Posted: **Thu Apr 28, 2005 8:41 pm**

Yes, I had a bug somewhere. I started shortening my code and the bug disappeared by itlself. I don't even know what it was. :-)

Posted: **Thu May 05, 2005 8:38 pm**

Hello, having some troubles with this problem, too.. Is it possible that pieces of the same color are disconnected?

Posted: **Thu May 05, 2005 9:19 pm**

No, there are always exactly 3 pieces. I checked it with an assert().

Posted: **Mon May 09, 2005 4:08 pm**

Abednego wrote:No, there are always exactly 3 pieces. I checked it with an assert().

That's right, thank you. My problems lied in oversimplificated understanding of the problem. Now I managed to solve it with some nice time.

Posted: **Wed Oct 26, 2005 10:28 pm**

I ve tried to solve this problem in this way:
-First I exmaine each component if they can move, when i find such a component, change it's bricks to another charachter that would be considered as a free space.
then I use dfs to find whether there is another component that can pass through free spaces out of the cube, if i find such a component i print "RGB" otherwise i print the type of the component that was found in the first step. if no component found in the first step i print "NO".
but i got WA too many times, and i 've checked it a lot with no success.
i wonder if anyone could give me some tricky I/O or read ma code, and tell me what's wrong with that.
thx in advance

Code: Select all

#include <iostream>
#include <string>
using namespace std;

char cube[12][12][12];
int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
char col[3]={'R','G','B'};
int mat[3];
int n;
int mark[100][100][100];

int dfs(int x,int y,int z,int a)
{
        mark[x+20][y+20][z+20]=1;
        for(int l=0;l<6;l++)
        {
                int flag=1;
                for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                                for(int k=1;k<=n;k++)
                                        if(cube[i][j][k]==col[a]&&cube[i+x+dir[l][0]][j+y+dir[l][1]][k+z+dir[l][2]]!=cube[i][j][k]
                                        &&cube[i+x+dir[l][0]][j+y+dir[l][1]][k+z+dir[l][2]]!=' ')
                                        {
                                                flag=0;
                                                i=j=k=1000;
                                        }
                if(flag)return 1;
        }
        for(int l=0;l<6;l++)
                if(!mark[x+dir[l][0]+20][y+dir[l][1]+20][z+dir[l][2]+20])
                {
                        int flag=1;
                        for(int i=1;i<=n;i++)
                                for(int j=1;j<=n;j++)
                                        for(int k=1;k<=n;k++)
                                        {
                                                if(cube[i][j][k]==col[a]&&cube[i+x+dir[l][0]][j+y+dir[l][1]][k+z+dir[l][2]]!=cube[i][j][k]
                                                &&cube[i+x+dir[l][0]][j+y+dir[l][1]][k+z+dir[l][2]]!='!')
                                                {
                                                        flag=0;
                                                        i=j=k=1000;
                                                }
                                        }
                        if(flag&&dfs(x+dir[l][0],y+dir[l][1],z+dir[l][2],a))return 1;
                }
        return 0;
}

int poss(int c, int d)
{
        for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                        for(int k=1;k<=n;k++)
                                if(cube[i][j][k]==col[c]
                                &&cube[i+dir[d][0]][j+dir[d][1]][k+dir[d][2]]!=cube[i][j][k]
                                &&cube[i+dir[d][0]][j+dir[d][1]][k+dir[d][2]]!=' ')
                                        return 0;
        for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                        for(int k=1;k<=n;k++)
                                if(cube[i][j][k]==col[c])
                                        cube[i][j][k]='!';
        return 1;
}

main()
{
        while(cin>>n)
        {
                //cout<<n<<endl;
                for(int i=0;i<=n+1;i++)
                        for(int j=0;j<=n+1;j++)
                                for(int k=0;k<=n+1;k++)
                                        cube[i][j][k]=' ';
                memset(mat,0,sizeof mat);
                for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                                for(int k=1;k<=n;k++)
                                {
                                        cin>>cube[i][j][k];
                                        if(cube[i][j][k]=='R')mat[0]=-1;
                                        else if(cube[i][j][k]=='G')mat[1]=-1;
                                        else if(cube[i][j][k]=='B')mat[2]=-1;
                                }
                int flag=0;
                for(int d=0;d<6;d++)
                        for(int c=0;c<3;c++)
                                if(mat[c]==-1&&poss(c,d))
                                {
                                        flag=1;
                                        mat[c]=1;
                                        c=1000;d=1000;
                                }
                if(flag)
                {
                        flag=0;
                        for(int i=0;i<3;i++)
                        {
                                memset(mark,0,sizeof mark);
                                if(mat[i]==-1&&dfs(0,0,0,i))
                                        flag=1;
                        }
                        if(flag)
                                cout<<"RGB";
                        else
                                for(int i=0;i<3;i++)
                                        if(mat[i]==1)
                                                cout<<col[i];
                }
                else
                        cout<<"NO";
                cout<<endl;
        }
        return 0;
}

Posted: **Wed Oct 29, 2014 5:25 pm**

Help me.....i can't understand what the problem says and the input and output........pls can anyone give me the explanation what the problem says and why the input and output looks like????????

thanks in advance

Posted: **Wed Oct 29, 2014 9:10 pm**

Read this thread.

Next time post in the existing thread.

OJ Board

10103 - Karpovich blocks

10103 - Karpovich blocks

Re: 10103 - Karpovich blocks