2

ループせずに直線での到達可能性をテストしようとする場合、ビットボード表現を使用できます。チェス、バイトとして表されるボードの行または列、および正方形 X のルークが正方形 T のターゲットをキャプチャできるかどうかという問題を想像してみてください。

T: ターゲット、X: 開始、O: 他の占有されたマス、_: 空のマスとする

これらの記号を使用して、考えられるシナリオを視覚化すると便利であることがわかりました。

// __OXO___ -> X is between others on both sides
// __XOO___ -> X is leftmost of others
// __OOX___ -> X is rightmost of other others
//A: T_OOX___ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//B: T_XOO___ -> Target left of X, X leftmost    -> T > X and O < X -> reachable
//C: __OXO_T_ -> Target right of X, X embedded   -> T < X and ???? -> NOT reachable
//D: __OOX_T_ -> Target right of X, X rightmost  -> T < X and ???? -> reachable

ここには、AD からラベル付けされた 4 つの興味深いケースがあります。ケースAとBは扱いやすいです。

しかし、ケース C と D はそうではありません。> または < を単純にテストして、ターゲットが到達可能かどうか、またはパスがブロックされているかどうかを確認することはできません。

ただし、バイト内のビットをミラーリングすることにより、C、D を A、B に変換することができます。つまり、ビット 0 -> ビット 7、ビット 1 -> ビット 6、...

その反転を行うための最適化された実装があるかどうかは誰にもわかりませんか?

編集: 別のケースがあることに気付きました: E: OT__X___ ... 私の理論はうまくいきませんが、疑問は残ります。:)

4

4 に答える 4

2

このテストは、元に戻さずに実行できます。x、t、およびoが例のようにビットマスクである場合 (とxにtは正確に 1 つのビットが設定されており、これらのビットは では設定されていません)、次のようにとoの間のビットを含むビットマスクを作成できます。tx

tx = t | x
txhi = tx & (tx - 1)
return (txhi - 1) ^ (tx - 1)

これは、1 を減算すると、「100...000」で終わるビット パターンが「011...111」に置き換えられることを使用します。次に、このマスクが と交差するかどうかを簡単に確認できますo。

于 2015-01-23T21:25:02.450 に答える