組み合わせ爆発を再現してみた

最近話題になっている動画を見てみた。
http://www.youtube.com/watch?v=Q4gTV4r0zRs
ちょっと再現出来ないか嫁と娘が風呂に入っているときにぱぱっとプログラムを書いてみた。

class CombinationExplosion
{
public:
	CombinationExplosion( int size ):m_size(size){
		m_trace = new bool*[size+2] + 1;
		for( int i = -1; i < size+1; ++i ){
			m_trace[i] = new bool[size+2] + 1;
		}
	}
	virtual ~CombinationExplosion(){
		for( int i = -1; i < m_size+1; ++i ){
			delete[] (m_trace[i] - 1);
		}
		delete[] (m_trace - 1);
	}

	long long Execute()
	{
		//初期化
		for( int y = -1; y < m_size+1; ++y ){
			for( int x = -1; x < m_size+1; ++x ){
				if ( 0 <= y && y < m_size && 0 <= x && x < m_size ){
					m_trace[y][x] = false;
				}else{
					m_trace[y][x] = true;
				}
			}
		}
		//開始
		return Trace( 0, 0 );
	}

protected:
	long long Trace( int x, int y ){
		if( m_trace[y][x] ){
			return 0;
		}
		if( x == m_size-1 && y == m_size-1 ){
			return 1;
		}
		m_trace[y][x] = true;
		const long long result =
			Trace( x + 1, y ) +
			Trace( x - 1, y ) +
			Trace( x, y + 1 ) +
			Trace( x, y - 1 );
		m_trace[y][x] = false;
		return result;
	}


private:
	int m_size;
	bool** m_trace;
};

動画とサイズがちょっと違って、動画はマスの数ですがこちらは格子点の数なので1だけずれます。
アルゴリズムは単純に総当たりです。各格子点上で４方向に進む選択肢があるのでそれぞれ数えます。実際やってみたら確かに普通のパソコンでは６×６(上記プログラムだと７×７)が限界っぽいですね。うちのパソコンで数分かかりました。怖いのでその先はやってません。
ちなみに最新のアルゴリズムってなんだろう？興味があるが調べようがないな・・・。