>>482
以前、お題スレ Part6の984 の問題で作ったものをそのまま流用。
左上から部屋番号1,2,3,...36（右下）として、部屋同士の接続を定義。
言語C++： http://ideone.com/1Nj1eU
5x5なら1秒以内で終わるのですが、6x6はideoneではタイムオーバーでした。
計算するときはn=6にして計算して下さい。自分のところでは計算に70秒程度。
正直合ってるかどうかわかりません。

結果：
6x6:
全1262816通り
最短距離10（252通り）
最長距離34（10180通り）

ちなみに・・・
2x2：全2通り
最短距離2（2通り）
最長距離2（2通り）
3x3：全12通り
最短距離4（6通り）
最長距離8（2通り）
4x4：全184通り
最短距離6（20通り）
最長距離14（32通り）
5x5：全8512通り
最短距離8（70通り）
最長距離24（104通り）