DouKaku?

棒倒し法も空間計算量がO(n)ですね。
すみません勘違いしてました。

私の考えたアルゴリズムと同じです。
棒倒し法の1行バッファ版と言えるようです。

以下、n=5, m=5の迷路の例でアルゴリズムを解説します。

・最初の行
Ｓ■■■■■■■■■■■←
まずバッファを用意して、全て壁にします。

・1行目(奇数行)
Ｓ■■■■■■■■■■■
１■★■★■★■★■★■←
★の箇所に穴を開けます。

Ｓ■■■■■■■■■■■
１■Ａ■Ｂ■Ｃ■Ｄ■Ｅ■←
穴を開けた場所をＡ～Ｅとします。

Ｓ■■■■■■■■■■■
１■Ａ★Ｂ★Ｃ★Ｄ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。

Ｓ■■■■■■■■■■■
１■Ａ▲Ｂ★Ｃ★Ｄ★Ｅ■←
たとえば▲に穴を開ける場合。

Ｓ■■■■■■■■■■■
１■ＡＡＡ★Ｃ★Ｄ★Ｅ■←
ＡとＢの領域が結合されるため、Ｂ領域をＡ領域に統合します。
仮にＢ領域に飛び地があっても、それもＡ領域に統合します。
また、★の左右が同じ領域だった場合は、穴を開けてはいけません。
ループ経路が出来てしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■←
この調子で穴を開けていきます。
全ての★を乱数で決定したら1行確定です。

・2行目(偶数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ☆Ａ☆Ａ☆Ａ★Ｅ■←
☆の箇所を壁にします。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■Ａ■Ａ■Ａ■Ｅ■←
★の箇所はすでに壁なので特に何もしません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■☆■☆■☆■☆■Ｅ■←
☆の箇所を壁にするかどうかを乱数で決定します。

ただし、残り１つになっているＥの列は壁になってはいけません。
また、４つの☆は３つまでは壁にしてもよいですが、
最後のひとつは壁にしてしてはいけません。
４つとも壁にしてしまうと
　Ｓ■■■■■■■■■■■
　１■ＡＡＡＡＡＡＡ■Ｅ■
　２■■■■■■■■■Ｅ■←
こうなって、Ａの領域に侵入できなくなってしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■←
乱数を使って結局２箇所を壁にすることになりました。
全ての☆を乱数で決定したら1行確定です。

・3行目(奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ■★■Ａ■★■Ｅ■←
1行目と同じく、★の箇所に穴を開けてＢ,Ｃ領域と
します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ★Ｂ★Ａ★Ｃ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。


あとは同じように、
偶数行→奇数行→偶数行→・・・
と繰り返します。


・9行目(最後の一つ前の行&奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ■Ｃ■Ｃ■Ｃ■←
最後の一つ前の行は辻褄あわせが必要です。
具体的には、すべての領域を統合しなければなりません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ★Ｃ■Ｃ■Ｃ■←
今回は、たまたまＡ領域とＣ領域しかないため、
★の箇所の壁を取り除けばＯＫです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ★Ａ☆Ｃ★Ｃ★Ｃ■
★☆の箇所に穴を開けるか乱数で決定します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ★Ａ★Ａ■
☆確定まで。
この例では、☆以外はたまたま左右が同じ領域なので、
選択肢がありません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ａ領域とＣ領域が統合されたため、
残りの★も穴をあけられなくなりました。

・最後の行
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ｅ■■■■■■■■■■■
全て壁で埋めます。

これでおしまいです。


私の書いたJavaコードだと出力無しで1372ミリ秒でした。
　　PentiumM 2.1GHz
　　java version "1.6.0_02"
　　Java(TM) SE Runtime Environment (build 1.6.0_02-b05)
　　Java HotSpot(TM) Server VM (build 1.6.0_02-b05, mixed mode)