以下のように対角位置で連なっている16枚の矩形がある。これを4x4の正方形になるように並べ替える。但し矢印が全て上を向くようにしなければならない。
A,Bに示した矩形はどこに配置されるか?
今年の車検の時に付けたETCを今日始めて使った。ちょっと緊張したけど,バーが開くと気持ちが良いものだ。
問題を見るとプログラムを作って解けそうな問題だ。矩形が16個しか無いから簡単に虱潰し出来そう。問題となるのはこれをどうやってデータ構造に表現するかということ。
最初矩形を順に4x4に配置していくことを考えた。
find( level) { 右に配置できる? find( level+1); 上に配置できる? find( level+1); 左に配置できる? find( level+1); 下に配置できる? find( level+1); }
だけど実は
を見ると,上下左右を考えるだけではダメなことが判る。
というように斜めも考えなければならない。何となく面倒な感じがする。そこで次に考えたのは,矩形を連結している部分に順に番号を振り,それをどこに配置すれば良いか考えるようにした。
これら0〜16の数字を以下の矩形上に配置することを考える。
例えば,10が7に配置されたとき,11は3,1,11,13の何れかに配置される可能性がある。
そうするとこれを虱潰すコードは以下のようになる。
find( level, nextpos) { if( nextposの右上の点が存在すれば) find( level+1, nextposの右上の点); if( nextposの左上の点が存在すれば) find( level+1, nextposの左上の点); if( nextposの左下の点が存在すれば) find( level+1, nextposの左下の点); if( nextposの右下の点が存在すれば) find( level+1, nextposの右下の点); }
後はこれに終了条件と制約条件を追加する。
終了条件はlevelが16になったとき,nextposがlevel=0の時と同じ位置になること。
制約条件は同じ矩形を踏まないことと,矢印が出現したlevelで矢印が上を向くことである。
find( level, nextpos) { if( level==16) { if( 出発点に戻ったか?) Find; return; } if( 同じ矩形を踏んだ?) return; if( level==2 && 矢印の向きが上でない) return; if( level==3 && 矢印の向きが上でない) return; if( level==7 && 矢印の向きが上でない) return; if( level==8 && 矢印の向きが上でない) return; if( level==12 && 矢印の向きが上でない) return; if( level==13 && 矢印の向きが上でない) return; if( nextposの右上の点が存在すれば) find( level+1, nextposの右上の点); if( nextposの左上の点が存在すれば) find( level+1, nextposの左上の点); if( nextposの左下の点が存在すれば) find( level+1, nextposの左下の点); if( nextposの右下の点が存在すれば) find( level+1, nextposの右下の点); }
最初の点は0〜24の25箇所を調べるので以下のようなコードになる。
level = 0; for( i=0; i< 25; i++) { if( iの右上の点が存在すれば) find( level+1, iの右上の点); if( iの左上の点が存在すれば) find( level+1, iの左上の点); if( iの左下の点が存在すれば) find( level+1, iの左下の点); if( iの右下の点が存在すれば) find( level+1, iの右下の点); }
25箇所の位置について,次の移動先を以下の構造体で表現する。
struct struct_nextpos { int rt, lt, lb, rb; // 0〜24 int rtbox, ltbox, lbbox, rbbox; // 0〜15 } nextpos[25]; int visit[16+1];// 訪問位置(0〜24) int box[16+1]; // 踏んだ矩形(0〜15),初期値を-1に設定しておく
struct_nextpoosに初期値を設定する関数は以下の通り。
void init() { for( int i=0; i< 25; i++) { nextpos[i].rt = i-5+1; nextpos[i].lt = i-5-1; nextpos[i].lb = i+5-1; nextpos[i].rb = i+5+1; nextpos[i].rtbox = i/5*4 + i%5 - 4; nextpos[i].ltbox = i/5*4 + i%5 - 4 - 1; nextpos[i].lbbox = i/5*4 + i%5 - 1; nextpos[i].rbbox = i/5*4 + i%5; } for( i=0; i< 5; i++) { nextpos[i].rt = -1; nextpos[i].lt = -1; nextpos[20+i].lb = i+5-1; nextpos[20+i].rb = i+5+1; } for( i=0; i< 25; i+=5) { nextpos[4+i].rt = -1; nextpos[i].lt = -1; nextpos[i].lb = -1; nextpos[4+i].rb = -1; } for( i=0; i< 16; i++) { box[i] = -1; } }
ここまでは順調に来た。後は向きを考えるだけ。連結している矩形を並べ替えてみると以下のようになる。
初期状態は2の時右,3の時上,7の時上,8の時左,12の時右,13の時右を向いている。
以下の7の位置に注目すると,7から右上は0°回転,左上は90°回転,左下は180°回転,右下は240°回転する。
このことを考慮してfind()の引数に回転を加えた結果find()とmain()は以下のようになる。
void find( int level, int nexti, int nextbox, int rotate) { visit[level] = nexti; if( level == 16) { // 出発点に戻ったか? if( nexti == visit[0]) { ps( "発見\n"); for( int k=0; k<= level; k++) { ps( "%2d ", visit[k]); } ps( "\n"); } return; } if( box[nextbox] >= 0) return; // このBOXは既に訪問済み box[nextbox] = 1; // 2:右 // 3:上 // 7:上 // 8:左 // 12:右 // 13:右 if( (level == 2 && ((rotate+3)%4) != 0) || (level == 3 && ((rotate+0)%4) != 0) || (level == 7 && ((rotate+0)%4) != 0) || (level == 8 && ((rotate+1)%4) != 0) || (level == 12 && ((rotate+3)%4) != 0) || (level == 13 && ((rotate+3)%4) != 0)) { box[nextbox] = -1; return; } rotate += 4- (rotate%4); // 正規化 // 右上,左上,左下,右下を順に調べる。 if( nextpos[nexti].rt != -1) find( level+1, nextpos[nexti].rt, nextpos[nexti].rtbox, rotate+0); if( nextpos[nexti].lt != -1) find( level+1, nextpos[nexti].lt, nextpos[nexti].ltbox, rotate+1); if( nextpos[nexti].lb != -1) find( level+1, nextpos[nexti].lb, nextpos[nexti].lbbox, rotate+2); if( nextpos[nexti].rb != -1) find( level+1, nextpos[nexti].rb, nextpos[nexti].rbbox, rotate+3); box[nextbox] = -1; } int main( int argc, cstring argv[]) { init(); int level = 0; for( int i=0; i< 25; i++) { visit[level] = i; if( nextpos[i].rt != -1) find( level+1, nextpos[i].rt, nextpos[i].rtbox, 0); if( nextpos[i].lt != -1) find( level+1, nextpos[i].lt, nextpos[i].ltbox, 1); if( nextpos[i].lb != -1) find( level+1, nextpos[i].lb, nextpos[i].lbbox, 2); if( nextpos[i].rb != -1) find( level+1, nextpos[i].rb, nextpos[i].rbbox, 3); visit[level] = -1; } return 0; }
答えは1件出力されました。
解速度
即