Skip to content

Instantly share code, notes, and snippets.

@pioh

pioh/skbn.cpp

Created February 9, 2018 21:40
Show Gist options
  • Save pioh/bc15f1be43137c528f83af3d90c04048 to your computer and use it in GitHub Desktop.
Save pioh/bc15f1be43137c528f83af3d90c04048 to your computer and use it in GitHub Desktop.
Download ZIP
skbn
Raw
skbn.cpp
#pragma comment(linker, "/STACK:134217728")
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using std::cin;
using std::cout;
int m, n, sz, num, numb;
char ** map;
char ** keys;
char ** box_map;
char ** boxes;
char ** sht;
int shts;
int now_step = 0;
int sx, sy;
long long ** pascale;
struct State_struct
{
State_struct * par;
char * states;
char x, y;
bool checked;
};
State_struct * states;
State_struct * s;
int states_size;
int * idn, * idl;
long int idns, idls;
/******************************************************************************************************/
/******************************************************************************************************/
void Cin_Map ();
bool Is_Key ( int x, int y );
void Set_Keys ();
void Clear_Map ();
bool Is_Happy ();
int Run ();
long double C_n_k ( int n, int k );
long long & C_n_k_pasc ( int n, int k );
void States_Init ();
void Set_Pascale ();
void Swap ();
void Push ( int ind );
int Get_State ();
void Save ( int st );
int Start ();
bool Check_Boxes ();
bool Set_Box_Map_El ( int x, int y );
int Get_El_State ( int x, int y );
void Set_Box_Map ();
/******************************************************************************************************/
/******************************************************************************************************/
int last, nows, first;
void Print_Way ( State_struct * in )
{
bool b = false;
if ( (*in).par != 0 )
{
Print_Way ( (*in).par );
}
for ( int i = 0; i < numb; i++ )
{
if (*(boxes[ i ]) != (*in).states [ i ])
{
b = true;
*(boxes[ i ]) = (*in).states [ i ];
}
}
if ( (*in).par != 0 )
{
if ( (*in).x > sx )printf ( "%c", (b)? 'R':'r' );
if ( (*in).x < sx )printf ( "%c", (b)? 'L':'l' );
if ( (*in).y > sy )printf ( "%c", (b)? 'D':'d' );
if ( (*in).y < sy )printf ( "%c", (b)? 'U':'u' );
}
sx = (*in).x;
sy = (*in).y;
}
int main ()
{
char st [ 100 ] = "";
gets ( st );
Cin_Map ();
Set_Box_Map ();
Set_Keys ();
Clear_Map ();
States_Init ();
Start ();
Print_Way ( &(s [ last ]) );
// while ( 1 );
return 0;
}
/******************************************************************************************************/
/******************************************************************************************************/
int Go ( int dx, int dy )
{
static int t;
if ( ( sx + dx ) >= 0 )if ( ( sy + dy ) >= 0 )if ( ( sx + dx ) < m )if ( ( sy + dy ) < n )
{
if ( map [ sx + dx ][ sy + dy ] == '.' )
{
sx += dx;
sy += dy;
t = Get_State ();
if ( s [ t ].checked )
{
sx -= dx;
sy -= dy;
return false;
}
if ( Is_Happy () )
{Save ( t );s [ t ].par = &(s [ nows ]);
sx -= dx;
sy -= dy;
last = t;
return true;
}
Save ( t );s [ t ].par = &(s [ nows ]);
Push ( t );
sx -= dx;
sy -= dy;
return false;
}else if ( map [ sx + dx ][ sy + dy ] == '#' )if ( ( sx + dx + dx ) >= 0 )if ( ( sy + dy + dy ) >= 0 )if ( ( sx + dx + dx ) < m )if ( ( sy + dy + dy ) < n )if ( box_map [ sx + dx + dx ][ sy + dy + dy ] != '*' )
{
if ( map [ sx + dx + dx ][ sy + dy + dy ] == '.' )
{
map [ sx + dx + dx ][ sy + dy + dy ] = '#';
map [ sx + dx ][ sy + dy ] = '.';
sx += dx;
sy += dy;
t = Get_State ();
if ( s [ t ].checked )
{
sx -= dx;
sy -= dy;
map [ sx + dx + dx ][ sy + dy + dy ] = '.';
map [ sx + dx ][ sy + dy ] = '#';
return false;
}
if ( Is_Happy () )
{Save ( t );s [ t ].par = &(s [ nows ]);
sx -= dx;
sy -= dy;
map [ sx + dx + dx ][ sy + dy + dy ] = '.';
map [ sx + dx ][ sy + dy ] = '#';
last = t;
return true;
}
Save ( t );s [ t ].par = &(s [ nows ]);
Push ( t );
sx -= dx;
sy -= dy;
map [ sx + dx + dx ][ sy + dy + dy ] = '.';
map [ sx + dx ][ sy + dy ] = '#';
return false;
}
}
}
return false;
}
bool Calc ( int in )
{
sx = s [ in ].x;
sy = s [ in ].y;
for ( int i = 0; i < numb; i++ ) *(boxes[ i ]) = s [ in ].states [ i ];
nows = in;
if ( Go ( -1, 0 ) ) return true;
if ( Go ( 1, 0 ) ) return true;
if ( Go ( 0, -1 ) ) return true;
if ( Go ( 0, 1 ) ) return true;
return false;
}
int Run ()
{
Swap ();
for ( int i = 0; i < idls; i++ )
{
if ( Calc ( idl [ i ] ) ){ return true; }
}
if ( idns <= 0 ) return false;
now_step++;
return Run ();
}
/******************************************************************************************************/
/******************************************************************************************************/
void Save ( int st )
{
s [ st ].states = (char*) malloc ( numb * sizeof ( char ) );
if ( !s [ st ].states ){printf ( "Error %d", __LINE__ ); exit ( 0 ); }
for ( int i = 0; i < numb; i++ )
{
s [ st ].states [ i ] = *( boxes [ i ] );
}
s [ st ].x = sx;
s [ st ].y = sy;
s [ st ].checked = true;
s [ st ].par = 0;
}
int Start ()
{
if ( Is_Happy () ) return true;
int st = Get_State ();
first = st;
Save ( st );
Push ( st );
now_step++;
return Run ();
}
void Swap ()
{
int * idt = idn;
idn = idl;
idl = idt;
idls = idns;
idns = 0;
}
void Push ( int ind )
{
idn [ idns++ ] = ind;
}
/******************************************************************************************************/
/******************************************************************************************************/
void States_Init ()
{
Set_Pascale ();
states_size = (int)( ((int)C_n_k ( numb, num ) ) * ( shts - num ) );
idns = 0;
idls = 0;
idn = (int*) malloc ( states_size * sizeof ( int ) );
if ( !idn ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
idl = (int*) malloc ( states_size * sizeof ( int ) );
if ( !idl ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
s = states = (State_struct*) malloc ( states_size * sizeof ( State_struct ) );
if ( !s ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
for ( int i = 0; i < states_size; i++ )
{
states [ i ].checked = false;
}
}
long double C_n_k ( int N, int K )
{
return (( (N<K) ? 0 : ((K==0) ? 1 : ((N-K+1) / (long double )(K) * C_n_k(N,K-1))) ));
}
long long & C_n_k_pasc ( int n, int k )
{
return pascale [ n ][ k ];
}
void Set_Pascale ()
{
pascale = (long long**) malloc ( ( numb + 1 ) * sizeof ( long long* ) );
if ( !pascale ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
for ( int i = 0; i < ( numb + 1 ); i++ ){ pascale [ i ] = (long long*) malloc ( ( numb + 1 ) * sizeof ( long long ) ); if ( !pascale [ i ] ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); } }
for ( int i = 0; i <= numb; i++ )
{
for ( int j = 0; j <= i; j++ ) C_n_k_pasc ( i, j ) = (long long)C_n_k ( i, j );
}
}
int Get_State ()
{
long long i, shtt, out, lb;
out = 0;
i = 1;
lb = 0;
for ( int x = 1; x <= numb; x++ )
{
if ( (*(boxes [ x - 1 ])) == '#' )
{
for ( int j = ( lb + 1 ); j < x; j++ )
{
out += C_n_k_pasc ( numb - j, num - i );
}i++;
lb = x;
if ( i > num )break;
}
}
i = 1;
map [ sx ][ sy ] = '%';
for ( int x = 1; x <= shts; x++ )
{
if ( (*(sht [ x - 1 ])) == '#' ){ i++; }
else if ( (*(sht [ x - 1 ])) == '%' )
{
shtt = x - i;
}
}
map [ sx ][ sy ] = '.';
return ( out * ( shts - num ) + shtt );
}
/******************************************************************************************************/
/******************************************************************************************************/
/*void Cin_Map ()
{
scanf ( "%d%d", &n, &m );
m -= 2;
n -= 2;
sz = m * n;
map = (char**) malloc ( m * sizeof ( char * ) );
for ( int i = 0; i < m; i++ ) map [ i ] = (char*) malloc ( n * sizeof ( char ) );
char c;
int mi = 0, ni = 0;
char str [ 2000000 ];
gets ( str );
for ( int i = 0; i < sizeof ( str ); i++ )str [ i ] = 0;
while ( ( ni < ( n + 1 ) ) )
{
for ( int i = 0; i < sizeof ( str ); i++ )str [ i ] = 0;
gets ( str );
if ( ni > 0 )
for ( int k = 0; k < m; k++ )map [ k ][ ni - 1 ] = str[k + 1];
ni++;
}
for ( int i = 0; i < m; i++ )
{
for ( int j = 0; j < n; j++ )
{
if ( map [ i ][ j ] == '#' ) map [ i ][ j ] = '*';
else if ( map [ i ][ j ] == '+' ) map [ i ][ j ] = '%';
else if ( map [ i ][ j ] == ' ' ) map [ i ][ j ] = '.';
else if ( map [ i ][ j ] == '$' ) map [ i ][ j ] = '#';
else if ( map [ i ][ j ] == '*' ) map [ i ][ j ] = '$';
else if ( map [ i ][ j ] == '.' ) map [ i ][ j ] = 'x';
}
}
}*/
char Trans ( char c )
{
if ( c == '#' ) return '*';
else if ( c == '+' ) return '%';
else if ( c == ' ' ) return '.';
else if ( c == '$' ) return '#';
else if ( c == '*' ) return '$';
else if ( c == '.' ) return 'x';
else if ( c == '@' ) return '@';
return 0;
}
void Cin_Map ()
{
int sz_0 = 200;
map = (char**) malloc ( sz_0 * sizeof ( char * ) );
if ( !map ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
for ( int i = 0; i < sz_0; i++ ){ map [ i ] = (char*) malloc ( sz_0 * sizeof ( char ) ); if ( !map [ i ] ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); } }
m = 0;
n = 0;
char str [ 500 ];
int ni = 0, nj = 0, k;
for ( int i = 0; i < sizeof ( str ); i++ )str [ i ] = 0;
while ( gets ( str ) )
{
if ( !Trans(*str))break;
n++;
k = 0;
m = 0;
for ( k = 0; k < sz_0; k++ )
{
str [ k ] = Trans ( str [ k ] );
if ( str [ k ] ) m++;
}
for ( k = 0; k < ( sz_0 ); k++ )map [ k ][ ni ] = str [ k ];
ni++;
for ( int i = 0; i < sizeof ( str ); i++ )str [ i ] = 0;
}
sz = m * n;
/*for ( int j = 0; j < n; j++ )
{
for ( int i = 0; i < m; i++ )
{
printf ( "%c", map [ i ][ j ] );
}
printf ( "\n" );
}*/
}
void Set_Keys ()
{
num = 0;
for ( int i = 0; i < m; i++ )
{
for ( int j = 0; j < n; j++ )
{
if ( Is_Key ( i, j ) ) num++;
}
}
keys = (char**) malloc ( num * sizeof ( char* ) );
if ( !keys ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
num = 0;
for ( int i = 0; i < m; i++ )for ( int j = 0; j < n; j++ )if ( Is_Key ( i, j ) ) keys [ num++ ] = &map [ i ][ j ];
}
bool Is_Key ( int i, int j )
{
if ( ( map [ i ][ j ] == 'x' ) || ( map [ i ][ j ] == '%' ) || ( map [ i ][ j ] == '$' ) )return true;
return false;
}
void Clear_Map ()
{
for ( int i = 0; i < m; i++ )for ( int j = 0; j < n; j++ )
{
if ( ( map [ i ][ j ] == '@' ) || ( map [ i ][ j ] == '%' ) ){ sx = i; sy = j; }
if ( ( map [ i ][ j ] == 'x' ) || ( map [ i ][ j ] == '@' ) || ( map [ i ][ j ] == '%' ) ){ map [ i ][ j ] = '.'; }
if ( ( map [ i ][ j ] == '$' ) ) map [ i ][ j ] = '#';
}
shts = 0;
numb = 0;
for ( int i = 0; i < m; i++ )for ( int j = 0; j < n; j++ )
{
if ( box_map [ i ][ j ] != '*' ) numb++;
if ( map [ i ][ j ] != '*' ) shts++;
}
sht = (char**) malloc ( shts * sizeof ( char* ) );
boxes = (char**) malloc ( numb * sizeof ( char* ) );
if ( !sht ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
if ( !boxes ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
numb = 0;shts = 0;
for ( int i = 0; i < m; i++ )for ( int j = 0; j < n; j++ )
{
if ( box_map [ i ][ j ] != '*' ) boxes [ numb++ ] = &(map [ i ][ j ]);
if ( map [ i ][ j ] != '*' )sht [ shts++ ] = &(map [ i ][ j ]);
}
}
bool Is_Happy ()
{
for ( int i = 0; i < num; i++ )
{
if ( (*(keys[i])) != '#' ) return false;
}return true;
}
void Set_Box_Map ()
{
box_map = (char**) malloc ( m * sizeof ( char* ) );
if ( !box_map ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
for ( int i = 0; i < m; i++ )
{
box_map [ i ] = (char*) malloc ( n * sizeof ( char ) );
if ( !box_map [ i ] ) {printf ( "Error %d", __LINE__ ); exit ( 0 ); }
for ( int j = 0; j < n; j++ ){ box_map [ i ][ j ] = '.'; }
}
for ( int i = 0; i < m; i++ )
{
for ( int j = 0; j < n; j++ )
{
if ( Set_Box_Map_El ( i, j ) ) box_map [ i ][ j ] = '*';
}
}
}
int Get_El_State ( int x, int y )
{
int st [ 14 ]; for ( int i = 0; i < 14; i++ ) st [ i ] = 0;
if ( x == 0 ){ st [ 3 ]++; st [ 5 ]++; st [ 9 ]++; st [ 10 ]++; st [ 11 ]++; st [ 12 ]++; st [ 8 ]++; }
else if ( map [ x - 1 ][ y ] == '*' ){ st [ 3 ]++; st [ 5 ]++; st [ 9 ]++; st [ 10 ]++; st [ 11 ]++; st [ 12 ]++; st [ 8 ]++; }
if ( y == 0 ){ st [ 2 ]++; st [ 4 ]++; st [ 8 ]++; st [ 10 ]++; st [ 11 ]++; st [ 13 ]++; st [ 7 ]++; }
else if ( map [ x ][ y - 1 ] == '*' ){ st [ 2 ]++; st [ 4 ]++; st [ 8 ]++; st [ 10 ]++; st [ 11 ]++; st [ 13 ]++; st [ 7 ]++; }
if ( x == ( m - 1 ) ){ st [ 1 ]++; st [ 5 ]++; st [ 7 ]++; st [ 10 ]++; st [ 12 ]++; st [ 13 ]++; st [ 6 ]++; }
else if ( map [ x + 1 ][ y ] == '*' ) { st [ 1 ]++; st [ 5 ]++; st [ 7 ]++; st [ 10 ]++; st [ 12 ]++; st [ 13 ]++; st [ 6 ]++; }
if ( y == ( n - 1 ) ){ st [ 0 ]++; st [ 4 ]++; st [ 6 ]++; st [ 11 ]++; st [ 12 ]++; st [ 13 ]++; st [ 9 ]++; }
else if ( map [ x ][ y + 1 ] == '*' ){ st [ 0 ]++; st [ 4 ]++; st [ 6 ]++; st [ 11 ]++; st [ 12 ]++; st [ 13 ]++; st [ 9 ]++; }
for ( int i = 13; i >= 0; i-- )
{
if ( ( i > 9 ) && ( i < 14 ) ) if ( st [ i ] > 2 ) return 8;
if ( ( i > 5 ) && ( i < 10 ) ) if ( st [ i ] > 1 ) return 8;
if ( ( i > 3 ) && ( i < 6 ) ) if ( st [ i ] > 1 ) return i + 2;
if ( ( i >= 0 ) && ( i < 4 ) ) if ( st [ i ] > 0 ) return i + 2;
}
return 1;
}
bool Set_Box_Map_El ( int x, int y )
{
bool b;
if ( Is_Key ( x, y ) ) return false;
if ( map [ x ][ y ] == '*' )return true;
switch ( Get_El_State ( x, y ) )
{
case 8:
return true;
break;
case 1:
return false;
break;
case 2:
b = false;
for ( int k = x + 1; k < m; k++ )
{
if ( Is_Key ( k, y ) ){ b = true; break; }
if ( map [ k ][ y ] == '*' ) break;
if ( y < ( n - 1 ) )if ( map [ k ][ y + 1 ] != '*' ){ b = true; break; }
}if ( b ) return false;
for ( int k = x - 1; k >= 0; k-- )
{
if ( Is_Key ( k, y ) ){ b = true; break; }
if ( map [ k ][ y ] == '*' ) break;
if ( y < ( n - 1 ) )if ( map [ k ][ y + 1 ] != '*' ){ b = true; break; }
}if ( b ) return false;
return true;
break;
case 3:
b = false;
for ( int k = y + 1; k < n; k++ )
{
if ( Is_Key ( x, k ) ){ b = true; break; }
if ( map [ x ][ k ] == '*' ) break;
if ( x < ( m - 1 ) )if ( map [ x + 1 ][ k ] != '*' ){ b = true; break; }
}if ( b ) return false;
for ( int k = y - 1; k >= 0; k-- )
{
if ( Is_Key ( x, k ) ){ b = true; break; }
if ( map [ x ][ k ] == '*' ) break;
if ( x < ( m - 1 ) )if ( map [ x + 1 ][ k ] != '*' ){ b = true; break; }
}if ( b ) return false;
return true;
break;
case 4:
b = false;
for ( int k = x + 1; k < m; k++ )
{
if ( Is_Key ( k, y ) ){ b = true; break; }
if ( map [ k ][ y ] == '*' ) break;
if ( y > 0 )if ( map [ k ][ y - 1 ] != '*' ){ b = true; break; }
}if ( b ) return false;
for ( int k = x - 1; k >= 0; k-- )
{
if ( Is_Key ( k, y ) ){ b = true; break; }
if ( map [ k ][ y ] == '*' ) break;
if ( y > 0 )if ( map [ k ][ y - 1 ] != '*' ){ b = true; break; }
}if ( b ) return false;
return true;
break;
case 5:
b = false;
for ( int k = y + 1; k < n; k++ )
{
if ( Is_Key ( x, k ) ){ b = true; break; }
if ( map [ x ][ k ] == '*' ) break;
if ( x > 0 )if ( map [ x - 1 ][ k ] != '*' ){ b = true; break; }
}if ( b ) return false;
for ( int k = y - 1; k >= 0; k-- )
{
if ( Is_Key ( x, k ) ){ b = true; break; }
if ( map [ x ][ k ] == '*' ) break;
if ( x > 0 )if ( map [ x - 1 ][ k ] != '*' ){ b = true; break; }
}if ( b ) return false;
return true;
break;
case 6:
b = false;
for ( int k = x + 1; k < m; k++ )
{
if ( Is_Key ( k, y ) ){ b = true; break; }
if ( map [ k ][ y ] == '*' ) break;
if ( y < ( n - 1 ) )if ( y > 0 )if ( map [ k ][ y - 1 ] != '*' )if ( map [ k ][ y + 1 ] != '*' ){ b = true; break; }
}if ( b ) return false;
for ( int k = x - 1; k >= 0; k-- )
{
if ( Is_Key ( k, y ) ){ b = true; break; }
if ( map [ k ][ y ] == '*' ) break;
if ( y < ( n - 1 ) )if ( y > 0 )if ( map [ k ][ y - 1 ] != '*' )if ( map [ k ][ y + 1 ] != '*' ){ b = true; break; }
}if ( b ) return false;
return true;
break;
case 7:
b = false;
for ( int k = y + 1; k < n; k++ )
{
if ( Is_Key ( x, k ) ){ b = true; break; }
if ( map [ x ][ k ] == '*' ) break;
if ( x > 0 )if ( x < ( m - 1 ) )if ( map [ x - 1 ][ k ] != '*' )if ( map [ x + 1 ][ k ] != '*' ){ b = true; break; }
}if ( b ) return false;
for ( int k = y - 1; k >= 0; k-- )
{
if ( Is_Key ( x, k ) ){ b = true; break; }
if ( map [ x ][ k ] == '*' ) break;
if ( x > 0 )if ( x < ( m - 1 ) )if ( map [ x - 1 ][ k ] != '*' )if ( map [ x + 1 ][ k ] != '*' ){ b = true; break; }
}if ( b ) return false;
return true;
break;
}
return true;
}
bool Check_Boxes ()
{
for ( int i = 0; i < m; i++ )for ( int j = 0; j < n; j++ )if ( box_map [ i ][ j ] == '*' )if ( map [ i ][ j ] == '#' )return false;
return true;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment