CodeIQ：一筆書きでクルクル
私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「一筆書きでクルクル」（CodeIQ）を参照してください。
問題の概要
図のような横に4本、縦に5本の道路が並んだ格子状の地図があります。
この地図を元に、左上の地点から右下の地点まで移動します。
ただし、一度通った道は通れないものとします。
（交差することや、同じ点を通ることは問題ありません。）
直角に曲がる回数が標準入力から指定されるとき、ちょうど指定された回数だけ曲がって右下の地点にたどり着くような道順が何通りあるかを求め、標準出力に出力してください。
例えば、標準入力から2が与えられたとき、図の5通りがありますので、標準出力に「5」を出力します。
私のプログラム
C++で解答しています。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <deque>
using namespace std;
class Position {
public:
int now[2];
int path;
int direction[2];
int turned;
Position();
int move(int d[]);
private:
int getPathNum(int bef[], int now[]);
};
Position::Position(){
now[0] = 0;
now[1] = 0;
path = 0;
direction[0] = 0;
direction[1] = 0;
turned = -1;
}
int Position::getPathNum(int bef[], int now[]){
if(bef[0] == now[0]){
int r = (bef[1] < now[1] ? bef[1] : now[1]);
return 1 << (4*bef[0] + r);
}
else if(bef[1] == now[1]){
int r = (bef[0] < now[0] ? bef[0] : now[0]);
return 1 << (3*bef[1] + r + 16);
}
return -1;
}
int Position::move(int d[]){
int nxt[] = {now[0]+d[0], now[1]+d[1]};
if( (nxt[0] < 0) || (3 < nxt[0]) || (nxt[1] < 0) || (4 < nxt[1]) ){
return 0;
}
int r = getPathNum(now, nxt);
if((path & r) == r){
return 0;
}
else{
path |= r;
}
if(d[0] != direction[0] || d[1] != direction[1]){
turned += 1;
}
direction[0] = nxt[0] - now[0];
direction[1] = nxt[1] - now[1];
now[0] = nxt[0];
now[1] = nxt[1];
return 1;
}
int search(int n){
int Direction[][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int Goal[] = {3,4};
int ret = 0;
deque<Position> queue;
Position s;
queue.push_back(s);
while(queue.size() != 0){
Position now = queue.front();
queue.pop_front();
for(int i=0; i<4; i++){
Position nxt = now;
if(nxt.move(Direction[i]) == 0){
continue;
}
if(nxt.now[0] == Goal[0] && nxt.now[1] == Goal[1]){
if(nxt.turned == n){
ret += 1;
}
}
else if(nxt.turned <= n){
queue.push_back(nxt);
}
}
}
return ret;
}
int main(void){
char str[8] = {0};
int n = 0;
while( fgets(str, sizeof(str), stdin) != NULL ){
for(int i=0; str[i]; i++){
if((str[i] == '\r') || (str[i] == '\n')){
str[i] = 0;
}
}
if(strlen(str) == 0){
continue;
}
n = atoi(str);
printf("%d\n", search(n));
}
return 0;
}
解説
私は最初この問題をRubyで書いたのですが、n=21の時にローカルで0.8秒を若干切るくらいという微妙な性能だったのでC++で書き直しました。なのでもっと早いアルゴリズムがある可能性が高いです。
Positionクラス
現在の探索位置と移動を管理するためのクラスです。変数はそれぞれ次の意味を持ちます。
now: 現在の座標（格子点の位置）。[y,x]。左上が[0,0]で右下が[3,4]。
path: 過去の経路情報。
direction: 前回の移動の向き。[-1,0]、[1,0]、[0,-1]、[0,1]のいずれか。
turned: 曲がった回数。
変数の中でpathは少し工夫してあります。経路ですが単なるintの変数で、経路を表すのにbitフラグを使用しています。問題の経路（全ての辺）は24しかないので全部に番号を振ります。そして辺を通ったらその番号のビットを1にすることで通過を表します。
これはかなり性能に貢献します。経路をvectorなどにした場合、vectorのコピーやvectorに値が含まれるかの検索が時間のかかる処理になりますが、単なるintの変数としたことで変数の代入と1回のビット演算と比較だけになるので非常に高速です。
もう一つ、turnedが-1なのは最初directionが[-1,0]、[1,0]、[0,-1]、[0,1]のいずれでもない[0,0]で始まるため、1回余分にターンがカウントされてしまうためです。-1から始めることで最初の移動時に0にセットされることになります。
Position::getPathNum(int bef[], int now[])
このメンバ関数は前述の経路のためどの辺が何番かを返すために使います。
プログラムでは横の辺を左上から右下に0〜11、縦の辺を左上から右下に16〜27にしています。
位置は格子点なので移動前の位置(bef)と移動後の位置(now)をもらってどの辺を通ったかを計算します。
32行目と36行目の条件は横方向に移動したのか縦方向に移動したのかを判断します。座標の変化のあった方が移動方向になります。
33行目と37行目の条件は上下、左右どちら向きに移動しても同じ番号にするためのものです。befとnowの座標のうち変化のあった要素の中で小さい方を返すことで、横方向に移動している時は常に左側の格子点、上下に移動している時は上の格子点の座標を得ることができます。
これに基づいて辺の番号を計算します。befとnowの座標のうち小さい値を基準に番号を計算し、その番号だけ1を左シフトした値を返します。縦と横でビット位置が重複しないよう縦方向の場合は16を加えています。
Position::move(int d[])
移動を処理します。
引数dは移動方向で[-1,0]、[1,0]、[0,-1]、[0,1]のいずれかをもらいます。
現在の座標にdの値を加えると移動先の座標になります（44行目）。ただし、座標が範囲外になっていたらエラーリターンします（45〜47行目）。
次に経路が通過済みかをチェックします（49〜55行目）。先に説明したgetPathNum()で今回通過する辺の値を得ます。これで得た値とそれまでの経路情報（path）の論理和を取り、今回の値と同じならすでに通ったということになるのでエラーリターンします。初めて通る場合はpathに現在の値を加えます。
57〜61では進行方向を計算して更新しています（が、使うと思って書いたものの使わずに消し忘れています）。進行方向が変わった時にturnedを1増やします。
最後に現在位置を更新して終わりです。
serach(int n)
探索の本体です。基本的に幅優先探索です。
70行目のDirectionとGoalは定数で、進行方向のリストとゴール地点の座標です。
73行目のretは結果の値を保持する領域、74行目のqueueは探索中の地点を保持するためのキュー、75行目のsはスタート時のPositionオブジェクトです。77行目で初期状態としてqueueに登録します。
79〜99行目のループはqueueに値がある限り処理を繰り返すためです。
ループに入ったらキューの先頭を取り出します（80〜81行目）。
83〜98行目のループでDirectionの4つの進行方向に移動させます。
現在のPositionオブジェクトをコピーして（84行目）、移動します（86行目）。移動結果が移動できない場所（0が返った場合）は処理をやめて次の方向に進みます。
ゴールに到達しているかをチェックし（90行目）、到達していてターン回数が指定通りだったら結果回数をカウントアップします（91〜93行目）。
ゴールに達していない場合、ターン回数が指定の値以下のものだけをqueueに追加します（ターン回数が指定を超えてしまったものには可能性がないので捨てます）。
queueがなくなったら結果を返します。
雑感
ロジック的には（結構難しかったですが）特に問題なくできましたが、別のところでハマりました。
投稿したら結果が全部0というわけの分からないことに。
結局、コンストラクタでpathとturnedだけを初期化して他のパラメータを初期化しないというコードになっていたためでした（turnedは特別な値ですが、pathは0にして他の値は0にしていないというよく分からないことに）。
ただ、ローカル環境（OSXのCLang）でコンパイルしたものは正しく動いていたので、最初はCodeIQの実行環境とのI/O（特に入力）の違いを疑っていました。色々試して（デバッグコードをCodeIQで実行して）I/Oには問題がないということがわかり、Linuxのg++でコンパイルしたら動いたり、おかしかったりするのが判明して初期化漏れが判明しました。
しかし、OSXのClang（と言うよりLLVM?）はオブジェクト生成時にメモリを0クリアしてくれるのでしょうか？