グリッドゲームに動きがないかどうかを判断する最も効率的な方法は？

Question

私は、同じ種類の3つの部分の行を作るためにグリッド内でゲームの部分を垂直または水平に1つの正方形に移動することができる単純なゲームを持っています。

ゲームのグリッドは幅8升、高さ7升です。動きが残っていないかどうかを確認する最も効率的な方法を見つけたいと思います。

私がこれまで持っていることは次のとおりです。

http://i.imgur.com/jY6wJvZ.png

私の思考私はC列をチェックする必要が水平にテストすることですどちらの側と同じピースタイプではなく、

垂直 - 私は行2と比較するだけで一致するものがないことを確認し、列5は行4と6と比較してマッチする必要があると考えました。

もしそれらのどれも一致しなければ、それ以上の動きはないでしょうか？

これが最も効率的な方法であるか、可能性のあるマッチを見逃す可能性があるかどうかはわかりませんが、私よりも脳が良い人なら、正しい方向に向けることができますか？

Answer 1

お客様の小切手は、移動がないことを保証するものではありません。例えば、左上隅を仮定した：

 *  * 
    a a b c . . . . 
* c c a b . . . . 
    b b d a . . . . 
    . . . . . . . . 
* . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 

実際、列Cには、細胞は、左または右のいずれかに等しくなく、行2には、細胞は、上記または下記のいずれかに等しいではありません。それでも、C1とC2を入れ替えて3行で3行作成することができます。

@Patashuが示唆しているように、ここでは、特に概念化のために、ナイーブな解決策が最もよいかもしれません。他の人があなたのコードを読んでいれば。私は一度に（境界のあるFIFOキュー内の）3つのセルを、行単位で、次に列単位で追跡し、3つのうち2つが一致した場合は、2番目から6番目の周囲のセルをチェックします。例えば、

. . . . . . . . 
    . . * . . * . . 
    . * . a a . * . 
    . . * . . * . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 

または

. . . . . . . . 
    . . . . * . . . 
    . . . a . a . . 
    . . . . * . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 

または

. . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . * . . 
    . . . . * . a a 

これら*「ED細胞は、（例えばa）と一致し、その後、あなたが知っている別の3-IN-のいずれかの場合a-rowが可能です。

Answer 2

ここは私の素朴なアルゴリズムです。明らかに、すべての配列アクセスは境界チェックを尊重する必要があります。

1）グリッドの各チェックボードの色を確認してください。読んラインで

x.x.x. 
.x.x.x 
x.x.x. 
.x.x.x 

スキャン、それを（すべてのxは水平に、その行を下る）（ヒント：% 2と* 2ここにあなたの友人になります）、次のやって：

1aにのみ、次のパターンによ）次のXのいずれかのも同じ色であれば、現在のタイルは、タイルと同じ色1下、私の右側にある場合は、それが連続して3です：

..... 
..XX. 
.Xx.X 
.X.xX 
..XX. 

図1b）の場合1つ下の左と同様です：

..... 
.XX.. 
X.xX. 
Xx.X. 
.XX.. 

（私はあなたがチェックされ、中央のタイルからのオフセットとしてのXの位置を符号化することになる - のようなアレイのように、{0、-1}、{ - 1,0}、{ - 1,1 }など）

（または、ここではチェックのために1の5×5の配列として、そうでない場合は0を実装することができます - この答えでどのように見えるかに似ていますが、プレイフィールドをスキャンします。これはより速いかもしれません。考えていない！

2）隣り合う2つのタイルが同じ色である場合は、どちらかが同じ色であれば、そのタイルを2つ上または下にチェックします。行の3：行の

. 
X 
. 
x 
x 
. 
X 

3）と同様に、左から右に読ん：

.X.xx.X 

注：これはにあらゆる可能なスワップをチェックする素朴なアルゴリズムよりも高速である場合、私は見当がつかないそれが3列に並んでいるかどうかを確認してください！結局のところ、両方のアルゴリズムはO（n^2）なので、実装の詳細によりますが速くなります。

1）ソリューションを実装するまでは最適化しないでください。使用している実際のケースについては、解決策が遅すぎる

2）あなたは、最適化、あなたがより速くそれを作ったチェック！（そして、それでも動作することを確認してください - コードを分解する最適化よりも悪いことはありません:)）

もちろん、これは最適化が楽しいものではありませんが、最適化の考え方に惑わされることはありませんすでに十分に速く、コードがあなたの心を行使したが、何もやっている;）