プログラムの実行結果は以下の通り。
Find 2件, 1.156秒 解:4本の辺を削除 ＋−０−＋−１−＋−２−＋ ｜ ｜ ｜ 12 Ａ Ｂ 14 Ｃ 15 ｜ ｜ ｜ ＋−３−＋−４−＋ ＋ ｜ ｜ ｜ ｜ 16 Ｄ 17 Ｅ 18 Ｆ 19 ｜ ｜ ｜ ｜ ＋ ＋−７−＋−８−＋ ｜ ｜ ｜ 20 Ｇ 21 Ｈ Ｉ 23 ｜ ｜ ｜ ＋−９−＋−10−＋−11−＋ 解:4本の辺を削除 ＋−０−＋−１−＋−２−＋ ｜ ｜ ｜ 12 Ａ 13 Ｂ Ｃ 15 ｜ ｜ ｜ ＋ ＋−４−＋−５−＋ ｜ ｜ ｜ ｜ 16 Ｄ 17 Ｅ 18 Ｆ 19 ｜ ｜ ｜ ｜ ＋−６−＋−７−＋ ＋ ｜ ｜ ｜ 20 Ｇ Ｈ 22 Ｉ 23 ｜ ｜ ｜ ＋−９−＋−10−＋−11−＋
4本の辺を削除したとき，正方形はＡＢＣＤＥＦＧＨＩと真ん中のＥの2つになる。
判りやすい図にすると以下のようになる。
プログラムのソースは以下の通り。
#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;
void print_rect( int r);
int main( int argc, cstring argv[])
{
// ＋−０−＋−１−＋−２−＋
// ｜ ｜ ｜ ｜
// 12 Ａ 13 Ｂ 14 Ｃ 15
// ｜ ｜ ｜ ｜
// ＋−３−＋−４−＋−５−＋
// ｜ ｜ ｜ ｜
// 16 Ｄ 17 Ｅ 18 Ｆ 19
// ｜ ｜ ｜ ｜
// ＋−６−＋−７−＋−８−＋
// ｜ ｜ ｜ ｜
// 20 Ｇ 21 Ｈ 22 Ｉ 23
// ｜ ｜ ｜ ｜
// ＋−９−＋−10−＋−11−＋
ulong rect[14] = { // 正方形の定義
/*A*/ bit0|bit3|bit12|bit13,
/*B*/ bit1|bit4|bit13|bit14,
/*C*/ bit2|bit5|bit14|bit15,
/*D*/ bit3|bit6|bit16|bit17,
/*E*/ bit4|bit7|bit17|bit18,
/*F*/ bit5|bit8|bit18|bit19,
/*G*/ bit6|bit9|bit20|bit21,
/*H*/ bit7|bit10|bit21|bit22,
/*I*/ bit8|bit11|bit22|bit23,
/*ABDE*/ bit0|bit1|bit6|bit7|bit12|bit16|bit14|bit18,
/*BCEF*/ bit1|bit2|bit7|bit8|bit13|bit17|bit15|bit19,
/*DEGH*/ bit3|bit4|bit9|bit10|bit16|bit20|bit18|bit22,
/*EFHI*/ bit4|bit5|bit10|bit11|bit17|bit21|bit19|bit23,
/*ABCDEFGHI*/ bit0|bit1|bit2|bit9|bit10|bit11|bit12|bit16|bit20|bit15|bit19|bit23,
};
int rect_size[14] = { // 1辺を1としたときの正方形の大きさ
1,1,1,1,1,1,1,1,1,4,4,4,4,9
};
ProcTime pt; // 処理時間計測
int max_lines_count = 0, lines_count;
set<int> find;
for( int i=0; i<= 0xFFFFFF; i++) { // 全ての辺の組み合わせを調べる
int num_rect = 0; // 14個中の正方形の数を勘定する
int find_rect[3]; // 見つけた正方形を記録する。3個以上正方形が見つかっても題意に反するので記録しない
for( int j=0; j< 14; j++) { // 14個の正方形を全て調べる
if( (rect[j]&i) == rect[j]) { // 正方形が見つかった
find_rect[num_rect] = j; // 正方形を記録する
num_rect++; // 個数も記録する
if( num_rect> 2) break; // 問題は2個の正方形なので3個以上の場合題意に反する。
}
}
if( num_rect == 2 && // 見つかった正方形の数が2個で
rect_size[find_rect[0]] != rect_size[find_rect[1]]) { // 正方形の大きさが異なる場合だけが題意を満たす
if( (lines_count=bitcount(i)) >= max_lines_count) { // 現在までの最大の辺数のものが見つかった
if( lines_count > max_lines_count) find.clear(); // 今までの辺数より大きい場合今まで記録したものは削除する
find.insert( i);
max_lines_count = lines_count; // 辺の数の最大値は今後これになる
}
}
}
pt.end();
ps( "Find %d件, %g秒\n", find.size(), pt.sec());
set<int>::iterator ite;
for( ite=find.begin(); ite != find.end(); ite++) { // 全ての結果を出力する
int i = *ite;
print_rect(i); // 結果表示
}
return 0;
}
// 以下出力部分，判りづらく本質的でないのでmainより後ろに持ってきた。
void Plus( int r, int bit) // plus()にするとコンパイルエラーになるのでPlus
{
if( r & bit) ps( "＋"); else ps( " ");
}
void horz( int r, int bit)
{
int b = 1;
if( r & bit) {
for( int i=0; i< 24; i++) {
if( bit & b) {
break;
}
b <<= 1;
}
ps( "−");
if( i < 10) ps( "%-.2s", "０１２３４５６７８９"+i*2);
else ps( "%2d", i);
ps( "−");
}
else {
ps( " ");
}
}
void vert( int r, int bit)
{
int b = 1;
if( r & bit) {
for( int i=0; i< 24; i++) {
if( bit & b) {
break;
}
b <<= 1;
}
if( i < 10) ps( "%-.2s", "０１２３４５６７８９"+i*2);
else ps( "%2d", i);
}
else {
ps( " ");
}
}
void abcd( cstring s)
{
ps( " ");
ps( "%s", s);
ps( " ");
}
void space( int r, int bit)
{
if( r & bit) ps( "｜");
else ps( " ");
ps( " ");
}
void print_rect( int r)
{
// ＋−０−＋−１−＋−２−＋
// ｜ ｜ ｜ ｜
// 12 Ａ 13 Ｂ 14 Ｃ 15
// ｜ ｜ ｜ ｜
// ＋−３−＋−４−＋−５−＋
// ｜ ｜ ｜ ｜
// 16 Ｄ 17 Ｅ 18 Ｆ 19
// ｜ ｜ ｜ ｜
// ＋−６−＋−７−＋−８−＋
// ｜ ｜ ｜ ｜
// 20 Ｇ 21 Ｈ 22 Ｉ 23
// ｜ ｜ ｜ ｜
// ＋−９−＋−10−＋−11−＋
ps( "解:%d本の辺を削除\n", 24-bitcount(r));
// ＋−０−＋−１−＋−２−＋
Plus(r,bit0|bit12);
horz(r,bit0);
Plus(r,bit0|bit1|bit13);
horz(r,bit1);
Plus(r,bit1|bit2|bit14);
horz(r,bit2);
Plus(r,bit2|bit15);
ps( "\n");
// ｜ ｜ ｜ ｜
space(r,bit12);
space(r,bit13);
space(r,bit14);
space(r,bit15);
ps( "\n");
// 12 Ａ 13 Ｂ 14 Ｃ 15
vert(r,bit12);
abcd("Ａ");
vert(r,bit13);
abcd("Ｂ");
vert(r,bit14);
abcd("Ｃ");
vert(r,bit15);
ps( "\n");
// ｜ ｜ ｜ ｜
space(r,bit12);
space(r,bit13);
space(r,bit14);
space(r,bit15);
ps( "\n");
// ＋−３−＋−４−＋−５−＋
Plus(r,bit12|bit3|bit16);
horz(r,bit3);
Plus(r,bit13|bit3|bit4|bit17);
horz(r,bit4);
Plus(r,bit14|bit4|bit5|bit18);
horz(r,bit5);
Plus(r,bit15|bit5|bit19);
ps( "\n");
// ｜ ｜ ｜ ｜
space(r,bit16);
space(r,bit17);
space(r,bit18);
space(r,bit19);
ps( "\n");
// 16 Ｄ 17 Ｅ 18 Ｆ 19
vert(r,bit16);
abcd("Ｄ");
vert(r,bit17);
abcd("Ｅ");
vert(r,bit18);
abcd("Ｆ");
vert(r,bit19);
ps( "\n");
// ｜ ｜ ｜ ｜
space(r,bit16);
space(r,bit17);
space(r,bit18);
space(r,bit19);
ps( "\n");
// ＋−６−＋−７−＋−８−＋
Plus(r,bit16|bit6|bit20);
horz(r,bit6);
Plus(r,bit17|bit6|bit7|bit21);
horz(r,bit7);
Plus(r,bit18|bit7|bit8|bit22);
horz(r,bit8);
Plus(r,bit19|bit8|bit23);
ps( "\n");
// ｜ ｜ ｜ ｜
space(r,bit20);
space(r,bit21);
space(r,bit22);
space(r,bit23);
ps( "\n");
// 20 Ｇ 21 Ｈ 22 Ｉ 23
vert(r,bit20);
abcd("Ｇ");
vert(r,bit21);
abcd("Ｈ");
vert(r,bit22);
abcd("Ｉ");
vert(r,bit23);
ps( "\n");
// ｜ ｜ ｜ ｜
space(r,bit20);
space(r,bit21);
space(r,bit22);
space(r,bit23);
ps( "\n");
// ＋−９−＋−10−＋−11−＋
Plus(r,bit20|bit9);
horz(r,bit9);
Plus(r,bit21|bit9|bit10);
horz(r,bit10);
Plus(r,bit22|bit10|bit11);
horz(r,bit11);
Plus(r,bit23|bit11);
ps( "\n");
ps( "\n");
}