10103 - Karpovich blocks

[Abednego]

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. :-)

[Kyku]

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

[Abednego]

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

[Kyku]

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.

[smile2ka10]

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;
}

[LazyTym]

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

[brianfry713]

Read this thread.

Next time post in the existing thread.