矩形が配置されている座標には矩形を配置できないというルールの整数座標がある場合、矩形を配置できる座標を高速に調べる手法を探しています。
BitBoardを使うことで、bit演算だけで配置可能座標を調べることができると考え、BitBoardを用いて実装しています。
既に矩形が配置されていれば1、配置されていなければ0とする8x8のBitBoardに対して、配置したい矩形のbit列で片っ端からAND演算をし、結果が0の場合に矩形が配置できることがわかりますが、より速い手法を探しています。
(例えば黒の矩形が配置済みで1として、3x4の矩形を新しく配置したい場合、片っ端からAND演算をしていくと、左下が43となる座標がAND演算の結果0となり、配置できることがわかる)
bit演算のテクニックを使えばもっと速くすることができると考えていますが、BitBoardの様々な文献を読んでもチェスやオセロの場合に使われるテクニックばかりで、このような矩形を配置できるかどうかのテクニックが見つかりませんでした。
愚直に片っ端からAND演算を試す以上の手法があれば教えていただきたいです。
また、BitBoardに対して、特定のサイズの矩形が配置できないことが高速にわかる手法がありましたら、AND演算で走査する必要がなくなるため、ご存知でしたら加えて教えていただきたいです。
> 愚直に片っ端からAND演算を試す以上の手法があれば教えていただきたいです。
矩形を描いた履歴をとっていないのであれば全探索するより他ないと思いますが。
とっているのであれば座標から演算することも可能だと思いますが、領域の大きさがこの程度であれば素直に全探索する方が速いかもしれません。
(正直,BitBoard なるものを知らないですが)
右側2人とORをとり,その結果を上3人とORをとり,結果が0ならいける,みたいな???
座標 43 を例にすると…
自身と44と45でORをとっても0.(←シフトしてORしてシフトしてORして,みたいな手続きで?)
(他の全マスも同時に同じことをしたとして,その結果の上で)自身と35,27,19 のORをとっても0なので矩形の左下になれる,っていう.
(一律処理してれば,同時に座標 58 もOKだとわかる…のかな?)
ありがとうございます。
履歴を取る方法も検討したいと思います。