1

「タッチ」と呼ばれる方法が必要だと思います (連続的で、感情的ではありません)。個々の要素または要素のセットの隣にあるマトリックスの要素を特定する必要があります。少なくとも、目前の問題を解決するために私が考えた方法です。

以下のプログラムの行列 State は、たとえば水中の地形を表しています。水を下げていくと、やがて最高点が突き出て「島」になっていきます。「水位」が 34 のとき、要素 State[2,3] は島の単一点です。配列 atlantis は、その単一のポイントの座標を保持します。

さらに水位を下げると、追加のポイントが「水上」になります。追加の連続点は島の一部になり、それらの座標は配列 atlantis に追加されます。(たとえば、アトランティスの一部になる次の土地は、31 の State[3,4] になります。)

これを行う方法についての私の考えは、アトランティスの要素に触れている/隣接しているすべてのマトリックス要素を特定し、標高が最も高いものを見つけて、配列アトランティスに追加することです。1 つの要素の隣にある要素を探すこと自体が困難ですが、セット [i,j-1]、[i,j+1]、[i-1,j-1] を調べるコードを書くことができます。 、[i-1、j]、[i-1、j+1]、[i+1、j-1]、[i+1、J]、[i+1、j+1]。（私はそれを正しく理解したと思います。）

しかし、追加のポイントを追加すると、アトランティスのポイントをどのポイントが囲むかを決定するタスクがますます難しくなります。それが私の質問です。誰かがこれを行うためのメカニズムを思いつくことができますか? 私が知らないルビーの機能を使用した単純化されたアルゴリズムはありますか? (最も基本的なものを除くすべてが含まれます。) そのようなメソッドを記述できる場合、atlantis.touching を記述して、たとえば、現在アトランティスに隣接しているすべてのポイントのすべての座標を含む配列を取得できます。

少なくとも、私はこれができると考えています。他のアイデアは大歓迎です。そして、私と一緒に仕事をすることに興味を持ちそうな他の人を探すことができるパートナー サイトを知っている人がいれば、それは素晴らしいことです。

# create State database using matrix
require 'matrix'

State=Matrix[ [3,1,4,4,6,2,8,12,8,2],
              [6,2,4,13,25,21,11,22,9,3,],
              [6,20,27,34,22,14,12,11,2,5],
              [6,28,17,23,31,18,11,9,18,12],
              [9,18,11,13,8,9,10,14,24,11],
              [3,9,7,16,9,12,28,24,29,21],
              [5,8,4,7,17,14,19,30,33,4],
              [7,17,23,9,5,9,22,21,12,21,],
              [7,14,25,22,16,10,19,15,12,11],
              [5,16,7,3,6,3,9,8,1,5] ]

#find sate elements contiguous to island
atlantis=[[2,3]]

find all state[i,j] "touching" atlantis
4

1 に答える 1

0

現在露出しているエリアの周りのポイントをチェックするだけでは、すべてのケースをカバーできるようには思えません。次に露出するポイントが新しい島の始まりだったとしたらどうでしょうか?

私は次のようにします：別の配列を持っています-sorted高さでソートされたポイントを含む配列を呼び出しましょう。水位を上げるたびに、新しい水位よりも高いすべての要素を外しsortedて上にポップしますatlantis。

実際、このようにすれば、個別sortedの配列は必要ありません。水上ではないatlantis最高点のインデックスを保存するだけで、基本的に 2 つの配列が 1 つにまとめられます。一方は水上にあり、もう一方は水面より下にあります。

それが役立つことを願っています!

于 2012-07-27T03:38:01.217 に答える