#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <Windows.h>
using namespace std;
struct XYZ
{
WORD x, y, z;
};
enum
{
M_UNKNOWN,
M_R, // Right
M_L, // Left
M_F, // Forward
M_B, // Backward
M_RF, // Right & forward
M_LF, // Left & forward
M_RB, // Right & backward
M_LB, // Left & backward
M_D, // Down
M_D_R, // Down & right
M_D_L, // Down & left
M_D_F, // Down & forward
M_D_B, // Down & backward
M_D_RF, // Down & right & forward
M_D_LF, // Down & left & forward
M_D_RB, // Down & right & backward
M_D_LB, // Down & left & backward
M_U, // Up
M_U_R, // Up & right
M_U_L, // Up & left
M_U_F, // Up & forward
M_U_B, // Up & backward
M_U_RF, // Up & right & forward
M_U_LF, // Up & left & forward
M_U_RB, // Up & right & backward
M_U_LB, // Up & left & backward
MAX_MOVE_DIRECTIONS
};
enum
{
F_R = 0x01,
F_D_R = 0x02,
F_U_R = 0x04,
F_L = 0x08,
F_D_L = 0x10,
F_U_L = 0x20,
F_F = 0x40,
F_D_F = 0x80,
F_U_F = 0x100,
F_B = 0x200,
F_D_B = 0x400,
F_U_B = 0x800,
F_RF = 0x1000,
F_D_RF = 0x2000,
F_U_RF = 0x4000,
F_LF = 0x8000,
F_D_LF = 0x10000,
F_U_LF = 0x20000,
F_RB = 0x40000,
F_D_RB = 0x80000,
F_U_RB = 0x100000,
F_LB = 0x200000,
F_D_LB = 0x400000,
F_U_LB = 0x800000,
F_D = 0x1000000,
F_U = 0x2000000
};
typedef struct
{
DWORD Mask;
DWORD SubMask;
WORD MoveID;
} Mask_t;
Mask_t Masks[ 26 ] = {
{ F_R|F_F|F_RF|F_B|F_RB|F_U|F_U_R|F_U_F|F_U_RF|F_U_B|F_U_RB|F_D|F_D_R|F_D_F|F_D_RF|F_D_B|F_D_B|F_D_RB, F_R, M_R },
{ F_L|F_F|F_LF|F_B|F_LB|F_U|F_U_L|F_U_F|F_U_LF|F_U_B|F_U_LB|F_D|F_D_L|F_D_F|F_D_LF|F_D_B|F_D_B|F_D_LB, F_L, M_L },
{ F_F|F_R|F_L|F_RF|F_LF|F_U|F_U_F|F_U_R|F_U_L|F_U_RF|F_U_LF|F_D|F_D_F|F_D_R|F_D_L|F_D_RF|F_D_LF, F_F, M_F },
{ F_B|F_R|F_L|F_RB|F_LB|F_U|F_U_B|F_U_R|F_U_L|F_U_RB|F_U_LB|F_D|F_D_B|F_D_R|F_D_L|F_D_RB|F_D_LB, F_B, M_B },
{ F_RF|F_F|F_R|F_U|F_U_RF|F_U_F|F_U_R|F_D|F_D_RF|F_D_F|F_D_F|F_D_R, F_RF, M_RF },
{ F_LF|F_F|F_L|F_U|F_U_LF|F_U_F|F_U_L|F_D|F_D_LF|F_D_F|F_D_F|F_D_L, F_LF, M_LF },
{ F_RB|F_B|F_R|F_U|F_U_RB|F_U_B|F_U_R|F_D|F_D_RB|F_D_B|F_D_R, F_RB, M_RB },
{ F_LB|F_B|F_L|F_U|F_U_LB|F_U_B|F_U_L|F_D|F_D_LB|F_D_B|F_D_L, F_LB, M_LB },
{ F_U|F_U_R|F_U_L|F_U_F|F_U_B|F_U_RF|F_U_LF|F_U_RB|F_U_LB|F_R|F_L|F_F|F_B|F_RF|F_LF|F_RB|F_LB, F_U, M_U },
{ F_U_R|F_U|F_U_F|F_U_B|F_U_RF|F_U_RB|F_R|F_F|F_B|F_RF|F_RB|/**/F_D|F_D_R|F_D_F|F_D_B|F_D_RF|F_D_RB, F_U_R, M_U_R },
{ F_U_L|F_U|F_U_F|F_U_B|F_U_LF|F_U_LB|F_L|F_F|F_B|F_LF|F_LB|/**/F_D|F_D_L|F_D_F|F_D_B|F_D_LF|F_D_LB, F_U_L, M_U_L },
{ F_U_F|F_U|F_U_R|F_U_L|F_U_RF|F_U_LF|F_F|F_R|F_L|F_RF|F_LF|/**/F_D|F_D_R|F_D_L|F_D_RF|F_D_LF|F_D_F, F_U_F, M_U_F },
{ F_U_B|F_U|F_U_R|F_U_L|F_U_RB|F_U_LB|F_B|F_R|F_L|F_RB|F_LB|/**/F_D|F_D_R|F_D_L|F_D_RB|F_D_LB|F_D_B, F_U_B, M_U_B },
{ F_U_RF|F_U|F_U_R|F_U_F|F_RF|F_R|F_F|/**/F_D|F_D_R|F_D_F|F_D_RF, F_U_RF, M_U_RF },
{ F_U_LF|F_U|F_U_L|F_U_F|F_LF|F_L|F_F|/**/F_D|F_D_L|F_D_F|F_D_LF, F_U_LF, M_U_LF },
{ F_U_RB|F_U|F_U_B|F_U_R|F_RB|F_B|F_R|/**/F_D|F_D_R|F_D_B|F_D_RB, F_U_RB, M_U_RB },
{ F_U_LB|F_U|F_U_B|F_U_L|F_LB|F_B|F_L|/**/F_D|F_D_L|F_D_B|F_D_LB, F_U_LB, M_U_LB },
{ F_D|F_D_R|F_D_L|F_D_F|F_D_B|F_D_RF|F_D_LF|F_D_RB|F_D_LB|F_R|F_L|F_F|F_B|F_RF|F_LF|F_RB|F_LB, F_D, M_D },
{ F_D_R|F_D|F_D_F|F_D_B|F_D_RF|F_D_RB|F_R|F_F|F_B|F_RF|F_RB|/**/F_U|F_U_R|F_U_F|F_U_B|F_U_RF|F_U_RB, F_D_R, M_D_R },
{ F_D_L|F_D|F_D_F|F_D_B|F_D_LF|F_D_LB|F_L|F_F|F_B|F_LF|F_LB|/**/F_U|F_U_L|F_U_F|F_U_B|F_U_LF|F_U_LB, F_D_L, M_D_L },
{ F_D_F|F_D|F_D_R|F_D_L|F_D_RF|F_D_LF|F_F|F_R|F_L|F_RF|F_LF|/**/F_U|F_U_R|F_U_L|F_U_RF|F_U_LF|F_U_F, F_D_F, M_D_F },
{ F_D_B|F_D|F_D_R|F_D_L|F_D_RB|F_D_LB|F_B|F_R|F_L|F_RB|F_LB|/**/F_U|F_U_R|F_U_L|F_U_RB|F_U_LB|F_U_B, F_D_B, M_D_B },
{ F_D_RF|F_D|F_D_R|F_D_F|F_RF|F_R|F_F|/**/F_U|F_U_R|F_U_F|F_U_RF, F_D_RF, M_D_RF },
{ F_D_LF|F_D|F_D_L|F_D_F|F_LF|F_L|F_F|/**/F_U|F_U_L|F_U_F|F_U_LF, F_D_LF, M_D_LF },
{ F_D_RB|F_D|F_D_B|F_D_R|F_RB|F_B|F_R|/**/F_U|F_U_R|F_U_B|F_U_RB, F_D_RB, M_D_RB },
{ F_D_LB|F_D|F_D_B|F_D_L|F_LB|F_B|F_L|/**/F_U|F_U_L|F_U_B|F_U_LB, F_D_LB, M_D_LB }
};
vector<vector<vector<bool>>> Matrix;
WORD X, Y, Z;
WORD GetMoveDirection( XYZ From, XYZ To )
{
if( From.x < To.x && From.y == To.y && From.z == To.z )
return M_R;
if( From.x > To.x && From.y == To.y && From.z == To.z )
return M_L;
if( From.x == To.x && From.y < To.y && From.z == To.z )
return M_F;
if( From.x == To.x && From.y > To.y && From.z == To.z )
return M_B;
if( From.x < To.x && From.y < To.y && From.z == To.z )
return M_RF;
if( From.x > To.x && From.y < To.y && From.z == To.z )
return M_LF;
if( From.x < To.x && From.y > To.y && From.z == To.z )
return M_RB;
if( From.x > To.x && From.y > To.y && From.z == To.z )
return M_LB;
if( From.x == To.x && From.y == To.y && From.z < To.z )
return M_U;
if( From.x < To.x && From.y == To.y && From.z < To.z )
return M_U_R;
if( From.x > To.x && From.y == To.y && From.z < To.z )
return M_U_L;
if( From.x == To.x && From.y < To.y && From.z < To.z )
return M_U_F;
if( From.x == To.x && From.y > To.y && From.z < To.z )
return M_U_B;
if( From.x < To.x && From.y < To.y && From.z < To.z )
return M_U_RF;
if( From.x > To.x && From.y < To.y && From.z < To.z )
return M_U_LF;
if( From.x < To.x && From.y > To.y && From.z < To.z )
return M_U_RB;
if( From.x > To.x && From.y > To.y && From.z < To.z )
return M_U_LB;
if( From.x == To.x && From.y == To.y && From.z > To.z )
return M_D;
if( From.x < To.x && From.y == To.y && From.z > To.z )
return M_D_R;
if( From.x > To.x && From.y == To.y && From.z > To.z )
return M_D_L;
if( From.x == To.x && From.y < To.y && From.z > To.z )
return M_D_F;
if( From.x == To.x && From.y > To.y && From.z > To.z )
return M_D_B;
if( From.x < To.x && From.y < To.y && From.z > To.z )
return M_D_RF;
if( From.x > To.x && From.y < To.y && From.z > To.z )
return M_D_LF;
if( From.x < To.x && From.y > To.y && From.z > To.z )
return M_D_RB;
if( From.x > To.x && From.y > To.y && From.z > To.z )
return M_D_LB;
return M_UNKNOWN;
}
WORD InvertMoveDirection( WORD Direction )
{
switch( Direction )
{
case M_R:
return M_L;
case M_L:
return M_R;
case M_F:
return M_B;
case M_B:
return M_F;
case M_RF:
return M_LB;
case M_LF:
return M_RB;
case M_RB:
return M_LF;
case M_LB:
return M_RF;
case M_U:
return M_D;
case M_U_R:
return M_D_L;
case M_U_L:
return M_D_R;
case M_U_F:
return M_D_B;
case M_U_B:
return M_D_F;
case M_U_RF:
return M_D_LB;
case M_U_LF:
return M_D_RB;
case M_U_RB:
return M_D_LF;
case M_U_LB:
return M_D_RF;
case M_D:
return M_U;
case M_D_R:
return M_U_L;
case M_D_L:
return M_U_R;
case M_D_F:
return M_U_B;
case M_D_B:
return M_U_F;
case M_D_RF:
return M_U_LB;
case M_D_LF:
return M_U_RB;
case M_D_RB:
return M_U_LF;
case M_D_LB:
return M_U_RF;
default:
return M_UNKNOWN;
}
}
bool IsCellPresent( WORD Dir, XYZ Point )
{
switch( Dir )
{
case M_R:
return ( Point.x + 1 < X && Matrix[ Point.z ][ Point.y ][ Point.x + 1 ] );
case M_L:
return ( Point.x - 1 >= 0 && Matrix[ Point.z ][ Point.y ][ Point.x - 1 ] );
case M_F:
return ( Point.y + 1 < Y && Matrix[ Point.z ][ Point.y + 1 ][ Point.x ] );
case M_B:
return ( Point.y - 1 >= 0 && Matrix[ Point.z ][ Point.y - 1 ][ Point.x ] );
case M_RF:
return ( Point.y + 1 < Y && Point.x + 1 < X && Matrix[ Point.z ][ Point.y + 1 ][ Point.x + 1 ] );
case M_LF:
return ( Point.y + 1 < Y && Point.x - 1 >= 0 && Matrix[ Point.z ][ Point.y + 1 ][ Point.x - 1 ] );
case M_RB:
return ( Point.y - 1 >= 0 && Point.x + 1 < X && Matrix[ Point.z ][ Point.y - 1 ][ Point.x + 1 ] );
case M_LB:
return ( Point.y - 1 >= 0 && Point.x - 1 >= 0 && Matrix[ Point.z ][ Point.y - 1 ][ Point.x - 1 ] );
case M_U:
return ( Point.z + 1 < Z && Matrix[ Point.z + 1 ][ Point.y ][ Point.x ] );
case M_U_R:
return ( Point.z + 1 < Z && Point.x + 1 < X && Matrix[ Point.z + 1 ][ Point.y ][ Point.x + 1 ] );
case M_U_L:
return ( Point.z + 1 < Z && Point.x - 1 >= 0 && Matrix[ Point.z + 1 ][ Point.y ][ Point.x - 1 ] );
case M_U_F:
return ( Point.z + 1 < Z && Point.y + 1 < Y && Matrix[ Point.z + 1 ][ Point.y + 1 ][ Point.x ] );
case M_U_B:
return ( Point.z + 1 < Z && Point.y - 1 >= 0 && Matrix[ Point.z + 1 ][ Point.y - 1 ][ Point.x ] );
case M_U_RF:
return ( Point.z + 1 < Z && Point.y + 1 < Y && Point.x + 1 < X && Matrix[ Point.z + 1 ][ Point.y + 1 ][ Point.x + 1 ] );
case M_U_LF:
return ( Point.z + 1 < Z && Point.y + 1 < Y && Point.x - 1 >= 0 && Matrix[ Point.z + 1 ][ Point.y + 1 ][ Point.x - 1 ] );
case M_U_RB:
return ( Point.z + 1 < Z && Point.y - 1 >= 0 && Point.x + 1 < X && Matrix[ Point.z + 1 ][ Point.y - 1 ][ Point.x + 1 ] );
case M_U_LB:
return ( Point.z + 1 < Z && Point.y - 1 >= 0 && Point.x - 1 >= 0 && Matrix[ Point.z + 1 ][ Point.y - 1 ][ Point.x - 1 ] );
case M_D:
return ( Point.z - 1 >= 0 && Matrix[ Point.z - 1 ][ Point.y ][ Point.x ] );
case M_D_R:
return ( Point.z - 1 >= 0 && Point.x + 1 < X && Matrix[ Point.z - 1 ][ Point.y ][ Point.x + 1 ] );
case M_D_L:
return ( Point.z - 1 >= 0 && Point.x - 1 >= 0 && Matrix[ Point.z - 1 ][ Point.y ][ Point.x - 1 ] );
case M_D_F:
return ( Point.z - 1 >= 0 && Point.y + 1 < Y && Matrix[ Point.z - 1 ][ Point.y + 1 ][ Point.x ] );
case M_D_B:
return ( Point.z - 1 >= 0 && Point.y - 1 >= 0 && Matrix[ Point.z - 1 ][ Point.y - 1 ][ Point.x ] );
case M_D_RF:
return ( Point.z - 1 >= 0 && Point.y + 1 < Y && Point.x + 1 < X && Matrix[ Point.z - 1 ][ Point.y + 1 ][ Point.x + 1 ] );
case M_D_LF:
return ( Point.z - 1 >= 0 && Point.y + 1 < Y && Point.x - 1 >= 0 && Matrix[ Point.z - 1 ][ Point.y + 1 ][ Point.x - 1 ] );
case M_D_RB:
return ( Point.z - 1 >= 0 && Point.y - 1 >= 0 && Point.x + 1 < X && Matrix[ Point.z - 1 ][ Point.y - 1 ][ Point.x + 1 ] );
case M_D_LB:
return ( Point.z - 1 >= 0 && Point.y - 1 >= 0 && Point.x - 1 >= 0 && Matrix[ Point.z - 1 ][ Point.y - 1 ][ Point.x - 1 ] );
default:
return false;
}
}
DWORD FindMask( WORD Dir )
{
for( WORD i = 0; i < 26; i++ )
{
if( Masks[ i ].MoveID == Dir )
return Masks[ i ].Mask;
}
return 0;
}
bool CanBeExcluded( WORD Dir, XYZ Point )
{
bool A = true, B = false;
DWORD Mask = FindMask( Dir );
for( WORD i = 0; i < 26; i++ )
{
if( IsCellPresent( Masks[ i ].MoveID, Point ) )
{
if( ( Mask & Masks[ i ].SubMask ) == Masks[ i ].SubMask )
B = true;
else
A = false;
}
}
return ( A && B );
}
void Exclusion( XYZ From, XYZ To, WORD OldC )
{
WORD Inv = InvertMoveDirection( GetMoveDirection( From, To ) );
if( CanBeExcluded( Inv, To ) )
{
Matrix[ To.z ][ To.y ][ To.x ] = false;
return;
}
WORD c = 1;
for( WORD i = M_R; i < MAX_MOVE_DIRECTIONS; i++ )
{
if( IsCellPresent( i, To ) )
c++;
}
if( c >= OldC )
Matrix[ To.z ][ To.y ][ To.x ] = false;
}
void EnvironmentCheck( WORD x, WORD y, WORD z, WORD * c )
{
XYZ tmp, From = { x, y, z };
vector<XYZ> Neighbours;
Neighbours.clear( );
if( IsCellPresent( M_R, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_L, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_F, From ) )
{
tmp.x = From.x;
tmp.y = From.y + 1;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_B, From ) )
{
tmp.x = From.x;
tmp.y = From.y - 1;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_RF, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y + 1;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_LF, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y + 1;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_RB, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y - 1;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_LB, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y - 1;
tmp.z = From.z;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D, From ) )
{
tmp.x = From.x;
tmp.y = From.y;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_R, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_L, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_F, From ) )
{
tmp.x = From.x;
tmp.y = From.y + 1;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_B, From ) )
{
tmp.x = From.x;
tmp.y = From.y - 1;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_RF, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y + 1;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_LF, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y + 1;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_RB, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y - 1;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_D_LB, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y - 1;
tmp.z = From.z - 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U, From ) )
{
tmp.x = From.x;
tmp.y = From.y;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_R, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_L, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_F, From ) )
{
tmp.x = From.x;
tmp.y = From.y + 1;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_B, From ) )
{
tmp.x = From.x;
tmp.y = From.y - 1;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_RF, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y + 1;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_LF, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y + 1;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_RB, From ) )
{
tmp.x = From.x + 1;
tmp.y = From.y - 1;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
if( IsCellPresent( M_U_LB, From ) )
{
tmp.x = From.x - 1;
tmp.y = From.y - 1;
tmp.z = From.z + 1;
Neighbours.push_back( tmp );
}
*c = *c + Neighbours.size( );
for( WORD i = 0; i < Neighbours.size( ); i++ )
{
XYZ To = { Neighbours[ i ].x, Neighbours[ i ].y, Neighbours[ i ].z };
Exclusion( From, To, *c );
}
Matrix[ z ][ y ][ x ] = false;
if( Neighbours.size( ) )
EnvironmentCheck( tmp.x, tmp.y, tmp.z, c );
}
bool Sorting( WORD A, WORD B )
{
return ( A > B );
}
int main( )
{
vector<WORD> IslandCells;
string Line;
cin >> X >> Y >> Z;
Matrix.resize( Z );
Matrix.clear( );
IslandCells.clear( );
for( WORD z = 0; z < Z; z++ )
{
getline( cin, Line );
Matrix[ z ].resize( Y );
Matrix[ z ].clear( );
for( WORD y = 0; y < Y; y++ )
{
Matrix[ z ][ y ].resize( X );
Matrix[ z ][ y ].clear( );
if( getline( cin, Line ) )
{
for( string::size_type i = 0; i < Line.size( ); i += 2 )
Matrix[ z ][ y ].push_back( Line[ i ] == '1' );
}
}
}
for( WORD z = 0; z < Z; z++ )
{
for( WORD y = 0; y < Y; y++ )
{
for( WORD x = 0; x < X; x++ )
{
if( Matrix[ z ][ y ][ x ] )
{
WORD c = 1;
EnvironmentCheck( x, y, z, &c );
IslandCells.push_back( c );
}
}
}
}
sort( IslandCells.begin( ), IslandCells.end( ), Sorting );
cout << IslandCells.size( ) << endl;
for( WORD i = 0; i < IslandCells.size( ); i++ )
cout << IslandCells[ i ] << endl;
return 0;
}
Add a code snippet to your website: www.paste.org