プログラム実行結果は以下の通り。
Find 4x4 順序は:DECAB . E E E C . . . E E E C . . . D D B C . . . D D B A . . . . . . . . . . . . . . . . . . . . . . . 5x5 順序は:DECAB . . . . . . . . . . . . . . C C C E E . . A B B E E . . . . . E E . . . . . D D . . . . . D D . . 2.437 秒
判りやすい図にすると以下の通り。
ちょっと長くて汚いけどプログラムのソースは以下の通り。
#include "puzutl.h"
const ulong bit0 = 0x00000001;
const ulong bit1 = 0x00000002;
const ulong bit2 = 0x00000004;
const ulong bit3 = 0x00000008;
const ulong bit4 = 0x00000010;
const ulong bit5 = 0x00000020;
const ulong bit6 = 0x00000040;
const ulong bit7 = 0x00000080;
const ulong bit8 = 0x00000100;
const ulong bit9 = 0x00000200;
const ulong bit10 = 0x00000400;
const ulong bit11 = 0x00000800;
const ulong bit12 = 0x00001000;
const ulong bit13 = 0x00002000;
const ulong bit14 = 0x00004000;
const ulong bit15 = 0x00008000;
const ulong bit16 = 0x00010000;
const ulong bit17 = 0x00020000;
const ulong bit18 = 0x00040000;
const ulong bit19 = 0x00080000;
const ulong bit20 = 0x00100000;
const ulong bit21 = 0x00200000;
const ulong bit22 = 0x00400000;
const ulong bit23 = 0x00800000;
const ulong bit24 = 0x01000000;
const ulong bit25 = 0x02000000;
const ulong bit26 = 0x04000000;
const ulong bit27 = 0x08000000;
const ulong bit28 = 0x10000000;
const ulong bit29 = 0x20000000;
const ulong bit30 = 0x40000000;
const ulong bit31 = 0x80000000;
const int64 bit32 = 0x0000000100000000L;
const int64 bit33 = 0x0000000200000000L;
const int64 bit34 = 0x0000000400000000L;
const int64 bit35 = 0x0000000800000000L;
const int64 bit36 = 0x0000001000000000L;
const int64 bit37 = 0x0000002000000000L;
const int64 bit38 = 0x0000004000000000L;
const int64 bit39 = 0x0000008000000000L;
const int64 bit40 = 0x0000010000000000L;
const int64 bit41 = 0x0000020000000000L;
const int64 bit42 = 0x0000040000000000L;
const int64 bit43 = 0x0000080000000000L;
const int64 bit44 = 0x0000100000000000L;
const int64 bit45 = 0x0000200000000000L;
const int64 bit46 = 0x0000400000000000L;
const int64 bit47 = 0x0000800000000000L;
const int64 bit48 = 0x0001000000000000L;
const int64 bit49 = 0x0002000000000000L;
const int64 bit50 = 0x0004000000000000L;
const int64 bit51 = 0x0008000000000000L;
const int64 bit52 = 0x0010000000000000L;
const int64 bit53 = 0x0020000000000000L;
const int64 bit54 = 0x0040000000000000L;
const int64 bit55 = 0x0080000000000000L;
const int64 bit56 = 0x0100000000000000L;
const int64 bit57 = 0x0200000000000000L;
const int64 bit58 = 0x0400000000000000L;
const int64 bit59 = 0x0800000000000000L;
const int64 bit60 = 0x1000000000000000L;
const int64 bit61 = 0x2000000000000000L;
const int64 bit62 = 0x4000000000000000L;
const int64 bit63 = 0x8000000000000000L;
inline int64 normalize_7x7( int64 v) // 7x7の図形を正規化する(左上に図形を移動する)
{
if( !v) return 0; // 永久ループ防止
while( !(v & (bit0|bit1|bit2|bit3|bit4|bit5|bit6))) {
v >>= 7;
}
while( !(v & (bit0|bit7|bit14|bit21|bit28|bit35|bit42))) {
v = ((v&(bit1|bit2|bit3|bit4|bit5|bit6))>>1)
| ((v&(bit8|bit9|bit10|bit11|bit12|bit13))>>1)
| ((v&(bit15|bit16|bit17|bit18|bit19|bit20))>>1)
| ((v&(bit22|bit23|bit24|bit25|bit26|bit27))>>1)
| ((v&(bit29|bit30|bit31|bit32|bit33|bit34))>>1)
| ((v&(bit36|bit37|bit38|bit39|bit40|bit41))>>1)
| ((v&(bit43|bit44|bit45|bit46|bit47|bit48))>>1)
;
}
return v;
}
inline int height_7x7( int64 v) // 7x7の図形の高さを取得する
{
int rowEnd = 0;
if( v & (bit42|bit43|bit44|bit45|bit46|bit47|bit48)) rowEnd = 7;
else if( v & (bit35|bit36|bit37|bit38|bit39|bit40|bit41)) rowEnd = 6;
else if( v & (bit28|bit29|bit30|bit31|bit32|bit33|bit34)) rowEnd = 5;
else if( v & (bit21|bit22|bit23|bit24|bit25|bit26|bit27)) rowEnd = 4;
else if( v & (bit14|bit15|bit16|bit17|bit18|bit19|bit20)) rowEnd = 3;
else if( v & (bit7 |bit8 |bit9 |bit10|bit11|bit12|bit13)) rowEnd = 2;
else if( v & (bit0 |bit1 |bit2 |bit3 |bit4 |bit5 |bit6 )) rowEnd = 1;
return rowEnd;
}
inline int width_7x7( int64 v) // 7x7の図形の幅を取得する
{
int colEnd = 0;
if( v & (bit6 |bit13|bit20|bit27|bit34|bit41|bit48)) colEnd = 7;
else if( v & (bit5 |bit12|bit19|bit26|bit33|bit40|bit47)) colEnd = 6;
else if( v & (bit4 |bit11|bit18|bit25|bit32|bit39|bit46)) colEnd = 5;
else if( v & (bit3 |bit10|bit17|bit24|bit31|bit38|bit45)) colEnd = 4;
else if( v & (bit2 |bit9 |bit16|bit23|bit30|bit37|bit44)) colEnd = 3;
else if( v & (bit1 |bit8 |bit15|bit22|bit29|bit36|bit43)) colEnd = 2;
else if( v & (bit0 |bit7 |bit14|bit21|bit28|bit35|bit42)) colEnd = 1;
return colEnd;
}
YesNo is_7x7_square_4x4( int64 A) // 7x7の図形の中の4x4の正方形か?
{
YesNo yn_square = NO, yn_rectangle = NO;
A = normalize_7x7(A);
int nbits = bitcount(A);
int height = height_7x7(A);
int width = width_7x7(A);
yn_square = false;
if( nbits != 4*4) return NO;
if( height*width == nbits) yn_rectangle = YES;
if( yn_rectangle && height == width) yn_square = YES;
return yn_square;
}
// 以上汎用部分
string finded_msg; // 見つかった図形
void dump_7x7( cstring msg, int64 A, int64 B, int64 C, int64 D, int64 E, char cA, char cB, char cC, char cD, char cE)
{
char cs[2048];
char buf[7][7];
int row, col;
char defC = '.';
for( row=0; row< 7; row++) {
for( col=0; col< 7; col++) {
buf[row][col] = defC;
if( A&1) { if(buf[row][col]==defC) buf[row][col] = cA; else buf[row][col]='?';}
if( B&1) { if(buf[row][col]==defC) buf[row][col] = cB; else buf[row][col]='?';}
if( C&1) { if(buf[row][col]==defC) buf[row][col] = cC; else buf[row][col]='?';}
if( D&1) { if(buf[row][col]==defC) buf[row][col] = cD; else buf[row][col]='?';}
if( E&1) { if(buf[row][col]==defC) buf[row][col] = cE; else buf[row][col]='?';}
A >>= 1;
B >>= 1;
C >>= 1;
D >>= 1;
E >>= 1;
}
}
sprintf( cs, "%s 順序は:%c%c%c%c%c\n", msg, cA, cB, cC, cD, cE); finded_msg += cs;
for( row=0; row< 7; row++) {
for( col=0; col< 7; col++) {
sprintf( cs, "%c ", buf[row][col]); finded_msg += cs;
}
sprintf( cs, "\n"); finded_msg += cs;
}
}
class rect { // 矩形
public:
rect( char c, int x, int y); // 矩形に文字と大きさを割り当てる
rect( const rect& r); // コピー
void mirror(); // MIRRORする,正方形でもMIRRORする
YesNo end_of_mirror(); // MIRROR出来たか?
void rotate90(); // 左に90度回転
int64 move( int& x, int& y); // (x,y)から矩形分座標位置を移動する,戻り値は図形のビット表現
char getchr() { return m_c;} // 矩形文字を得る(ダンプ出力用)
private:
char m_c; // 矩形文字('A','B','C','D','E','F'の何れか)
int m_x; // 座標位置
int m_y; //
YesNo m_yn_square; // 正方形か?
int m_mirror_count; // 正方形でない場合MIRRORした回数(初期値:0,最大値:1)
};
rect::rect( char c, int x, int y) // 座標位置を割り当てる
{
m_c = c;
m_x = x;
m_y = y;
m_yn_square = YES;
if( abs(m_x) != abs(m_y)) m_yn_square = NO; // x=yでないので正方形でない
m_mirror_count= 0;
}
rect::rect( const rect& r) // コピー
{
m_c = r.m_c;
m_x = r.m_x;
m_y = r.m_y;
m_yn_square = YES;
if( abs(m_x) != abs(m_y)) m_yn_square = NO;
m_mirror_count= 0;
}
void rect::mirror()
{
m_y = -m_y;
m_mirror_count++;
}
YesNo rect::end_of_mirror()
{
if( m_yn_square && m_mirror_count >= 1) return YES; // 正方形の場合mirrorは必要ない
if( m_mirror_count >= 2) return YES; // 長方形の場合は1回有効
return NO;
}
void rect::rotate90() // 90度左回転
{
int T = m_x;
m_x = -m_y;
m_y = T;
}
int64 get7x7bit( int x, int y, int dx, int dy) // (x,y)-(x+dx,y+dy)の図形を7x7のbitで取得する
{
x += dx;
y += dy;
if( x < 0) return 0;
if( y < 0) return 0;
if( x >= 7) return 0;
if( y >= 7) return 0;
y = 7-y-1;
int64 bit = 1;
bit <<= y*7;
bit <<= x;
return bit;
}
int64 rect::move( int& org_x, int& org_y)
{
int start_x = org_x;
int start_y = org_y;
if( m_x < 0) start_x += m_x;
if( m_y < 0) start_y += m_y;
org_x += m_x;
org_y += m_y;
if( org_x < 0 || org_x > 7 ||
org_y < 0 || org_y > 7) return 0; // 7x7の図形をはみ出た
int64 plane = 0;
int X = m_x;
int Y = m_y;
if( X < 0) { X = -X; }
if( Y < 0) { Y = -Y; }
for( int x=0; x< X; x++) {
for( int y=0; y< Y; y++) {
plane |= get7x7bit( start_x, start_y, x, y);
}
}
return plane;
}
rect R[6] = {
rect('A',1,1),
rect('B',2,1),
rect('C',3,1),
rect('D',2,2),
rect('E',3,2),
rect('F',3,3),
};
int64 plane4x4_03 = bit0|bit1|bit2|bit3|bit7|bit8|bit9|bit10|bit14|bit15|bit16|bit17|bit21|bit22|bit23|bit24;
int64 plane4x4_33 = bit3|bit4|bit5|bit6|bit10|bit11|bit12|bit13|bit17|bit18|bit19|bit20|bit24|bit25|bit26|bit27;
int64 plane4x4_30 = bit24|bit25|bit26|bit27|bit31|bit32|bit33|bit34|bit38|bit39|bit40|bit41|bit45|bit46|bit47|bit48;
int64 plane5x5 = bit14|bit15|bit16|bit17|bit18|bit21|bit22|bit23|bit24|bit25|bit31|bit32|bit38|bit39|bit45|bit46;
int64 planeF = bit28|bit29|bit30|bit35|bit36|bit37|bit42|bit43|bit44;
YesNo check4x4_ok( int start_x, int start_y, rect A, rect B, rect C, rect D, rect E) // 4x4の矩形が出来てFと重ならないか?
{
int x = start_x, y = start_y;
int64 planeA, planeB, planeC, planeD, planeE;
planeA = A.move(x,y);
planeB = B.move(x,y);
planeC = C.move(x,y);
planeD = D.move(x,y);
planeE = E.move(x,y);
if( !planeA |!planeB |!planeC |!planeD |!planeE) return NO;
if( (planeA | planeB | planeC | planeD | planeE) & planeF) return NO;
if( is_7x7_square_4x4( planeA | planeB | planeC | planeD | planeE)) {
dump_7x7( "4x4", planeA, planeB, planeC, planeD, planeE, A.getchr(), B.getchr(), C.getchr(), D.getchr(), E.getchr());
return YES;
}
return NO;
}
YesNo check4x4_with_rotate( int start_x, int start_y, rect A, rect B, rect C, rect D, rect E) // 回転を考慮する
{
for( int rotateA=0; rotateA< 4; rotateA++) {
A.rotate90();
for( int rotateB=0; rotateB< 4; rotateB++) {
B.rotate90();
for( int rotateC=0; rotateC< 4; rotateC++) {
C.rotate90();
for( int rotateD=0; rotateD< 4; rotateD++) {
D.rotate90();
for( int rotateE=0; rotateE< 4; rotateE++) {
E.rotate90();
if( check4x4_ok( start_x, start_y, A,B,C,D,E)) return YES;
}
}
}
}
}
return NO;
}
YesNo check4x4( int start_x, int start_y, rect start_A, rect start_B, rect start_C, rect start_D, rect start_E) // 4x4の矩形が出来るか?
{
for( rect A(start_A); !A.end_of_mirror(); A.mirror()) {
for( rect B(start_B); !B.end_of_mirror(); B.mirror()) {
for( rect C(start_C); !C.end_of_mirror(); C.mirror()) {
for( rect D(start_D); !D.end_of_mirror(); D.mirror()) {
for( rect E(start_E); !E.end_of_mirror(); E.mirror()) {
if( check4x4_with_rotate( start_x, start_y, A,B,C,D,E)) {
return YES;
}
}
}
}
}
}
return NO;
}
YesNo check5x5_ok( int start_x, int start_y, int64 plane, rect A, rect B, rect C, rect D, rect E)
{
int x = start_x, y = start_y;
int64 planeA, planeB, planeC, planeD, planeE;
planeA = A.move(x,y);
planeB = B.move(x,y);
planeC = C.move(x,y);
planeD = D.move(x,y);
planeE = E.move(x,y);
if( ( planeA | planeB | planeC | planeD | planeE ) == plane) {
dump_7x7( "5x5", planeA, planeB, planeC, planeD, planeE, A.getchr(), B.getchr(), C.getchr(), D.getchr(), E.getchr());
return YES;
}
return NO;
}
YesNo check5x5_with_rotate( int start_x, int start_y, int64 plane, rect A, rect B, rect C, rect D, rect E)
{
for( int rotateA=0; rotateA< 4; rotateA++) {
A.rotate90();
for( int rotateB=0; rotateB< 4; rotateB++) {
B.rotate90();
for( int rotateC=0; rotateC< 4; rotateC++) {
C.rotate90();
for( int rotateD=0; rotateD< 4; rotateD++) {
D.rotate90();
for( int rotateE=0; rotateE< 4; rotateE++) {
E.rotate90();
if( check5x5_ok( start_x, start_y, plane, A,B,C,D,E)) return YES;
}
}
}
}
}
return NO;
}
YesNo check5x5( int start_x, int start_y, int64 plane, rect start_A, rect start_B, rect start_C, rect start_D, rect start_E)
{
for( rect A(start_A); !A.end_of_mirror(); A.mirror()) {
for( rect B(start_B); !B.end_of_mirror(); B.mirror()) {
for( rect C(start_C); !C.end_of_mirror(); C.mirror()) {
for( rect D(start_D); !D.end_of_mirror(); D.mirror()) {
for( rect E(start_E); !E.end_of_mirror(); E.mirror()) {
if( check5x5_with_rotate( start_x, start_y, plane, A,B,C,D,E)) {
return YES;
}
}
}
}
}
}
return NO;
}
void test(rect A, YesNo yn_mirror, int num_rotate)
{
if( yn_mirror) A.mirror();
for( int i=0; i< num_rotate; i++) {
A.rotate90();
}
int x = 3, y = 3;
int64 planeA = A.move(x,y);
dump_7x7( "dump", planeA, 0, 0, 0, 0, 'A', 0, 0, 0, 0);
}
YesNo used[6];
int main( int argc, cstring argv[])
{
ProcTime pt;pt.start();
for( int a=0; a< 5; a++) {
used[a] = YES;
for( int b=0; b< 5; b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=0; c< 5; c++) {
if( used[c]) continue;
used[c] = YES;
for( int d=0; d< 5; d++) {
if( used[d]) continue;
used[d] = YES;
for( int e=0; e< 5; e++) {
if( used[e]) continue;
used[e] = YES;
finded_msg = "";
if( check4x4( 3,0,R[a],R[b],R[c],R[d],R[e]) ||
check4x4( 3,3,R[a],R[b],R[c],R[d],R[e]) ||
check4x4( 0,3,R[a],R[b],R[c],R[d],R[e])) {
if( check5x5( 3,0,plane5x5,R[a],R[b],R[c],R[d],R[e])) { ps( "Find\n%s", finded_msg.c_str());}//{ps( "Find5x5-3,0 a:%d,b:%d,c:%d,d:%d,e:%d\n",a,b,c,d,e);}
else if( check5x5( 3,3,plane5x5,R[a],R[b],R[c],R[d],R[e])) { ps( "Find\n%s", finded_msg.c_str());}//{ps( "Find5x5-3,3 a:%d,b:%d,c:%d,d:%d,e:%d\n",a,b,c,d,e);}
else if( check5x5( 0,3,plane5x5,R[a],R[b],R[c],R[d],R[e])) { ps( "Find\n%s", finded_msg.c_str());}//{ps( "Find5x5-0,3 a:%d,b:%d,c:%d,d:%d,e:%d\n",a,b,c,d,e);}
}
used[e] = NO;
}
used[d] = NO;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
pt.end();
ps( "%g 秒\n", pt.sec());
return 0;
}