問題タブ [flood-fill]

ゲーム キャラクターが到達できるグリッドのすべてのセルを検査する必要があります。これを行うには、キャラクターの位置から始めて、到達可能なすべてのセル (たとえば、壁によってブロックされていないセル) を見つけるために領域を「塗りつぶす」必要があります。

この図では、プレイヤーはPであり、プレイヤーを遮る壁は で表されていXます。プレーヤーが配置されている領域内のすべてのセルを検査する必要があります。

これを行うための優れた反復アルゴリズムはありますか? 現在、私はこれを再帰的に行っています。

I want to implement flood fill algorithm in my iphone app.I have been searching from long days and i have seen all the stack overflow answer but nothing helped me.

Please can any one post some sample application code which is using flood fill.

したがって、再帰は私の強みではありません。値がゼロの場合、intのベクトルのベクトルを1で埋める再帰的なfloodFill関数を作成することに挑戦しました。私のコードは、私を超えた理由でセグフォールトを続けています。おそらく私のコードはその音をより明確にするでしょう。

これは、洪水で埋められるグリッドです。

これは、基本的にベクトルの操作を支援する関数のセットである「グリッド」と呼ばれる私が作成したオブジェクトに属しています。グリッドの値はすべてゼロに初期化されます。

これは私のフラッドフィル関数です：

ここでの目的は、ポイントの値がゼロであるかどうかを関数にチェックさせ、ゼロである場合は1に変更することです。次に、その上のものが同じかどうかを確認する必要があります。これは、1が見つかるか、ベクトルの終わりに到達するまで行われます。次に、別の方向を試し、上記と同じ条件になるまで、以下同様に、洪水がいっぱいになるまで進み続けます。

誰かが私がこれを修正するのを手伝ってもらえますか？多分私に何が悪いのか教えてください？

ありがとう！

私はいくつかの会場のグループの予約可用性システムに取り組んでおり、特定の月の数日間の時間ブロックの可用性を生成するのに苦労しています。これはPHPのサーバー側で発生していますが、概念自体は言語に依存しません。JSなどでこれを行うことができます。

与えられたvenue_id、month、およびyear（たとえば、6/2012）を指定すると、その会場でその範囲で発生するすべてのイベントのリストが、UNIXタイムスタンプstartおよびとして表されendます。このデータはデータベースから取得されます。最小の長さ（会場ごとに異なる）の連続した時間ブロックが毎日存在する場合は、それを確立する必要があります。

たとえば、6/1に午後2時から午後7時の間にイベントがあります。最短時間は5時間なので、午前9時から午後2時まで、午後7時から午後12時までブロックが開いています。これは、6月の毎日2日、3日などに続きます。何も起こらない日もあれば、1〜3回のイベントもあります。

私が思いついた解決策はうまくいきましたが、データを生成するのに時間がかかりすぎました。基本的に、私はその月の毎日をループし、その日の15分ごとにタイムスタンプの配列を作成します。次に、その日からのイベントの期間を15分ループし、「取得された」タイムスロットをfalseとしてマークします。残りの部分には、空き時間と所要時間のタイムスタンプを含む配列があります。

次に、この配列をループして連続する時間ブロックを見つけ、それらが十分に長いかどうかを確認し（各会場には最小値があります）、そうであれば、開始と終了の説明テキストを確立する必要があります（つまり、午前9時から午後2時）。 。わあ！このすべてのループが完了するまでに、ユーザーは退屈になり、子犬のビデオを見るためにYouTubeに迷い込んでいます。30日ほど調べるのに何年もかかります。

この問題を解決するためのより速い方法はありますか？問題を要約すると、d日の時間範囲t1とt2が与えられた場合、最小時間ブロックmよりも長いdに残っている残り時間をどのように決定できますか。

このデータは、ユーザーが暦月間を移動するときに、AJAXを介してオンデマンドで収集されます。結果はページの読み込みごとにキャッシュされるため、ユーザーが2回目に7月に移動した場合、最初に生成されたデータが再利用されます。

役立つその他の詳細があれば、私に知らせてください。

編集

リクエストごとに、データベース構造（またはここで関連する部分）

イベントは常に15から始まります-：00、：15、：30、：45

いくつかの実際のタイムスタンプのデータダンプ：http：//pastebin.com/k1PRkj44

次のコードを実行すると、無限ループが発生しました。ブロックで囲まれたグリッド内で、この実装が実行される定義済みの正方形が開始されます。正方形は、訪問する必要がある場合は 1、訪問済みの場合は 2 とラベル付けされます。解決策が見つからないようで、いくつかの役立つヒントが欲しいです。

フラッドフィル機能が機能しないという問題が発生しています。この割り当ての目的は、P と C が配列内で接続されているかどうかを確認することです。フラッドフィル機能では、「_」を「P」に変更していないようです

サンプル入力

コード

どこかでメモリリークが発生しました。私は何度もそれを検索しました、そしてそれは私にはしっかりしているように見えます。私はただ..見つけることができません...それを見つける...わかりました、背景。これはスタック駆動のフラッドフィルであり、このコードのビットは、スタックに何かを追加する唯一の場所です。より多くのコードがあるので、誰もメモリリークを見つけることができない場合は、さらにいくつか投稿します。

これについて最も奇妙な部分があります。コードは1つの色+線画（pictexture）で正常に機能しますが、複数の色を使用して塗りつぶしバケットを使用すると、これらの奇妙なメモリリークが発生します。

編集：私はちょうど私が最も奇妙な部分に言及するのを忘れたことに気づきました。このコードは、開始色（青）以外の色を使用するまでは問題なく機能します。色を変えたら、青に戻っても壊れてしまいます。

フラッド フィル アルゴリズムの一般的な実装でスタック オーバーフローが発生しました。これを最適化する方法はありますか? このアルゴリズムを使用して、建物モデル内の明確なボイド ゾーンを見つけています。これらのモデルをボクセル化し、0 と 1 の単純化されたバージョンで表されるボクセル化された結果を解析します。0 と 1 は、ボクセルが存在するかどうかを表します。0 が存在し、1 が存在しません。次に、接続された 0 の個別のサブセット、つまり 3D 建物内の接続されたボイド スペースを見つける必要があります。

サンプル 2D 入力データの例をリストに格納すると、3D はリスト内の複数のエントリになります。(Z、Y、X) = (0、4、9)

ウィキペディアはいくつかの解決策を提案しましたが、それらを実装する方法がわかりません。これが既存のアルゴリズムです。より密度の高いデータ用に「sys.setrecursionlimit(10000)」を既に設定しています。これは一部の人にとっては問題ありませんが、建物モデルが何百もの部屋ではるかに複雑になるため、さらに密度の高いもの (Z, Y, X) = (50, 46, 22) またはそれ以上の場合、スタック オーバーフロー メッセージが表示されます。

再帰関数でエラー スタック オーバーフローが発生します。

コード：

ユーザーが指定した初期座標を取得し、文字をチェックしてから、必要に応じて変更する塗りつぶしメソッドを作成しようとしています。その後、隣接する正方形をチェックし、プロセスを繰り返します。いくつかの調査の後、フラッドフィルアルゴリズムに出会い、それを試した後(動作しますが、250 x 250 文字の配列の最大要件を満たすことができません)。

私の元のフラッド フィル アルゴリズムは次のとおりです。

テストの後、ウィキペディアで説明されているように Queue メソッドを試し始めました。この質問は、同様の問題に関して以前に尋ねられました。これまでのところ、次のコードを思いつきました。

最初の再帰的な方法は小さい値に対しては機能しましたが、配列が大きくなりすぎると機能しません。ただし、2 番目の方法では、Queues の経験が浅いために識別できないある種の無限ループに陥ります。最初のコード サンプルをより大きなサンプルで動作するように最適化するか、2 番目のコード サンプルを修正して結果が得られるようにするにはどうすればよいですか? これら2つのいずれかをコーディングする方法、または私が間違っていることを誰かが説明できますか?

ありがとう！

編集: 2 番目のコードで無限ループ エラーを見つけることができました (修正されました) が、キュー ベースの方法では完全な領域が埋められません。実際、再帰ベースの方法よりも領域が少なくなります。EDIT 2:正方配列で機能するようになりました。長方形配列でも機能することを確認するにはどうすればよいですか (2 番目の方法)。

画像上のポイントを指定して、そのポイントに接続されているすべてのポイントを塗りつぶしたいのですが、新しい画像に塗りつぶします。これを行うための素朴な方法は、元の画像を特別な魔法の色の値に塗りつぶすことです。次に、各ピクセルにアクセスし、この魔法の色の値を持つすべてのピクセルを新しい画像にコピーします。より良い方法があるに違いありません！