8

n*nたとえば、グリッドがありますn=10。黒と白の要素で埋める必要があります。すべての黒の要素には、1つ、2つ、または3つの黒の隣接要素が必要です。隣接要素が4つまたはゼロの黒い要素を含めることはできません。

この種のグリッドをどのように構築する必要がありますか？

編集：

具体的には、たとえば2つのforループで構築された2次元配列です。

n = 10
array = [][];
for ( x = 0; x < n; x++ ) {
    for ( y = 0; y < n; y++ ) {
        array[x][y] = rand(black/white)
    }
}

この擬似コードは、次のようなものを構築します。

現在

そして私が期待するのは：

期待される

4

3 に答える 3

5

明らかに、書き込みグリッド上に「ブラックパス」シェイプを生成しようとしています。

だからやってみましょう。

  • 白いグリッドから始めます。
  • その上にいくつかのカメをランダムに配置します。
  • 次に、グリッドが適切な白/黒のセル比を満たしていないときに、次の手順を実行します
    • 各カメをランダムな方向に1セル移動し、「3つ以下の黒い隣人」のルールに違反しない限り、黒く塗ります。
于 2012-10-30T15:10:39.330 に答える
2

たぶん、この python コードは役に立つかもしれません。その基本的な考え方は、グリッドのある種の幅優先トラバーサルを行い、黒く塗りつぶされたピクセルが 3 つ以下の黒の隣接ピクセルを持たないという制約を確実に尊重するようにすることです。グリッドの黒く塗りつぶされた部分に対応するグラフは、目的の結果のように見えるツリーです。

import Queue
import Image
import numpy as np
import random

#size of the problem
size = 50

#grid initialization
grid = np.zeros((size,size),dtype=np.uint8)

#start at the center
initpos = (size/2,size/2)

#create the propagation queue
qu = Queue.Queue()

#queue the starting point
qu.put((initpos,initpos))

#the starting point is queued
grid[initpos] = 1


#get the neighbouring grid cells from a position
def get_neighbours(pos):
  n1 = (pos[0]+1,pos[1]  )
  n2 = (pos[0]  ,pos[1]+1)
  n3 = (pos[0]-1,pos[1]  )
  n4 = (pos[0]  ,pos[1]-1)
  return [neigh for neigh in [n1,n2,n3,n4] 
                  if neigh[0] > -1 and \
                     neigh[0]<size and \
                     neigh[1] > -1 and \
                     neigh[1]<size \
         ]


while(not qu.empty()):
  #pop a new element from the queue
  #pos is its position in the grid
  #parent is the position of the cell which propagated this one
  (pos,parent) = qu.get()

  #get the neighbouring cells
  neighbours = get_neighbours(pos)

  #legend for grid values
  #0 -> nothing
  #1 -> stacked
  #2 -> black
  #3 -> white

  #if any neighbouring cell is black, we could join two branches
  has_black = False
  for neigh in neighbours:
    if neigh != parent and grid[neigh] == 2:
      has_black = True
      break

  if has_black:
    #blackening this cell means joining branches, abort
    grid[pos] = 3
  else:
    #this cell does not join branches, blacken it
    grid[pos] = 2

    #select all valid neighbours for propagation
    propag_candidates = [n for n in neighbours if n != parent and grid[n] == 0]
    #shuffle to avoid deterministic patterns
    random.shuffle(propag_candidates)
    #propagate the first two neighbours
    for neigh in propag_candidates[:2]:
      #queue the neighbour
      qu.put((neigh,pos))
      #mark it as queued
      grid[neigh] = 1

#render image
np.putmask(grid,grid!=2,255)
np.putmask(grid,grid<255,0)
im = Image.fromarray(grid)
im.save('data.png')

結果設定はこちらsize = 50

グリッド上の黒いツリー、幅 50

そしてもう1つの設定size = 1000

グリッド上の黒いツリー、幅 1000

木の根っこで遊ぶこともできます。

于 2012-10-30T17:05:05.180 に答える
1

ここに示したサイズでは、ちょっとした力ずくの実装を簡単に行うことができます。

要件を満たしているかどうかを確認する関数を作成します。単純に、すべてのセルを反復処理して隣接セルをカウントします。

その後、次のようにします。

Start out with a white grid.
Then repeatedly:
    pick a random cell
    If the cell is white:
        make it black
        call the grid checking routine.
        if the grid became invalid:
            color it gray to make sure you don't try this one again

do this until you think it took long enough, or there are no more white cells.
then make all gray cells white.

グリッドが大きい (数千ピクセル) 場合は、おそらくより効率的なアルゴリズムを探す必要がありますが、10x10 グリッドの場合、これは瞬時に計算されます。

于 2012-10-30T15:32:45.460 に答える