質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.13%

[パズル]2次元配列に格納された数値、上下左右を探索し合計が10になる組み合わせを探したい

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 168

hinatahinata

score 22

現在以下のようなルールのパズルゲームを制作中です。(C#)

  • 縦10マス × 横10マスのフィールドがある(2次元配列で管理)
  • 数字がかかれたブロックを1つずつフィールドに設置していく
  • 設置したブロックから上下左右につながったブロックの数値を再帰的に合計し、合計10になるブロックを消す

やりたいこと

フィールド上の数値をチェックし、合計10になる組み合わせを探す。
この時に、2次元配列の縦横のインデックス(位置)のリストを、組み合わせ毎に取得したい。
組み合わせ毎に取得したい理由は、「この組み合わせで10ができた!」という表示を個別に分けてしたいため。

フィールドが以下のような場合

[0] [1] [2] [3] [4]
[0]
[1]   1   4  
[2]   2 3 3
[3]     5 1  
[4]          
[5]          

得たい結果はインデックスを(x,y)と表現すると、

{(1,1) (1,2) (2,2) (3,2) (3,3)}
{(1,2) (2,2) (2,3)}
{(2,2) (3,2) (3,1)}


という、10ができる組み合わせ毎のインデックスリストを得たいです。

ぷよぷよのアルゴリズムような再帰関数での取得を考えましたが
インデックスの組み合わせを考えると上手く実装できません。
良いアルゴリズムはありますでしょうか。
実装例も合わせて提示していただけると助かります。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

check解決した方法

-1

自己解決しました。

過去にぷよぷよの探索アルゴリズムは作成したことがあるので違いだけ。
・上下左右に探索していき、その地点にある数値を足していくのは一緒。
・探索を進める時に、座標を履歴で保存する。
・空欄・壁に当たった時に探索を終了するのではなく、履歴の座標の上下左右をさらに探索する。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/02 09:52

    fanaさんの回答と何が違うのでしょうか?

    キャンセル

  • 2020/07/02 10:08 編集

    私の回答の文面が簡素すぎた(or etc)ために
    結果的にそこからでは具体的なアルゴリズムに結びつかなかった
    というだけの話かと思います.

    (結果が同じ話だったとしても)別のルートから自力でたどり着いたならば,それはそれで良いのではないでしょうか.
    本件の場合は,「書かれた回答の内容を用いて"自己解決"とする」というのとは違う雰囲気の様子に見えますので.

    キャンセル

-1

設置したブロックから上下左右につながったブロック

を見ていくだけで良いように思います.

塗りつぶしとか,
マップが升目なSLGの移動可能範囲探索
のような話を検索してみると良いかと.

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/06/30 23:56

    回答ありがとうございます。
    SLGの移動可能範囲探索アルゴリズムを調べましたが、今回の要件を満たすような実装が浮かびません。
    可能であれば、実装例を提示していただけると助かります。

    キャンセル

  • 2020/07/01 10:33

    それを実装することに個人的に得るものがないと思えるので私はやりません.
    単に隣接マスの値を次々に足し算していくつまらない処理です.
    スタックか何かに探索状況を積みつつ気のすむまで探索すればよいでしょう.
    処理効率とか枝刈りとかは度外視して,まずはやってみればよいのでは.
    「合計10になるパターンを,自分はどうやって探すだろうか?」というのを愚直にコード化すればよいでしょう.

    SLGの例で言えば,
    マスに書かれた数値が消費移動力だと見立てたときに,
    キャラクターが,移動力を全部使切る移動経路を探すことと等価に思えるけど,どうなんでしょう.

    キャンセル

  • 2020/07/02 09:35

    要件を満たす処理の流れをご提示いただきたかったのですが
    自己解決しましたので閉じさせていただきます。

    キャンセル

  • 2020/07/02 09:59

    ・質問を「自己解決」とする方法が存在するので,適切にそれを行ってください.

    ・「低評価」をくれた人はその理由をコメントで述べてください.
     例えば,本回答は私としては,(質問者が言うところの)"処理の流れ"の話にたどり着くのに十分な内容を示した回答であるつもりでおりましたが,読み手の立場から見てそれが不足と思えるのであれば,それが低評価の理由に該当します.

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.13%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる
  • トップ
  • C#に関する質問
  • [パズル]2次元配列に格納された数値、上下左右を探索し合計が10になる組み合わせを探したい