n * n 그리드에서 경로 생성

Question

과 같은 n*n 그리드가 있습니다. 흑백 요소로 채워야합니다. 모든 검은 색 요소는 하나, 둘 또는 세 개의 검은 이웃을 가져야합니다. 네 개 또는 네 이웃이있는 검정색 요소를 포함 할 수 없습니다.

어떻게 이런 종류의 격자를 만들어야합니까?

편집

:

:

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

이 의사 코드처럼 somethind 빌드 :

더 구체적으로는, 두 개의 for 루프가 예를 들어 내장 된 2 차원 배열이다

그리고 내가 기대하는 바는 다음과 같습니다.

Answer 1

분명히 쓰기 격자에 "검은 색 경로"모양을 생성하려고합니다.

그럼 그냥 해보 죠.

• 흰색 그리드로 시작하십시오.
• 무작위로 거북이를 놓습니다.
• 그런 다음, 적절한 화이트/블랙 세포의 비율을 충족하지 않는 그리드는, 임의의 방향으로 거북이에게 하나 개의 셀을 다음
  • 이동을하고 검은 색은 "더 이상 세 이상을 깰 그렇게하지 않는 페인트 동안 까만 이웃 사람 "규칙. 여기에 표시 크기와

Answer 2

, 당신은 쉽게 무력 구현의 비트에 갈 수 있습니다.

모든 셀을 반복하고 이웃 수를 계산하여 요구 사항을 충족하는지 확인하는 함수를 작성하십시오. 그 후

,이 같은 수행하여 그리드 (픽셀 수천) 큰

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. 

경우, 당신은 아마 더 효율적인 알고리즘을 찾아야한다,하지만 10 × 10 그리드 이것은에서 계산됩니다 플래시.

Answer 3

아마도이 파이썬 코드가 유용 할 수 있습니다. 기본적인 생각은 그리드의 첫 번째 탐색을 일종의 방식으로 수행하여 검정색 픽셀이 검은 색 이웃을 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

및 size = 1000

또한 트리의 루트로 재생할 수 있습니다 설정 다른 설정 결과입니다.