10103 - Karpovich blocks

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » 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. :-)
If only I had as much free time as I did in college...

Kyku
New poster
Posts: 12
Joined: Wed Dec 29, 2004 3:10 pm

Post by Kyku » 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?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu May 05, 2005 9:19 pm

No, there are always exactly 3 pieces. I checked it with an assert().
If only I had as much free time as I did in college...

Kyku
New poster
Posts: 12
Joined: Wed Dec 29, 2004 3:10 pm

Post by Kyku » 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.

smile2ka10
New poster
Posts: 13
Joined: Wed Oct 26, 2005 10:14 pm
Location: Iran
Contact:

Post by smile2ka10 » 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;
}

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

10103 - Karpovich blocks

Post by LazyTym » 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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10103 - Karpovich blocks

Post by brianfry713 » Wed Oct 29, 2014 9:10 pm

Read this thread.

Next time post in the existing thread.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”