如何編寫程序來查找完全封閉的圖塊？

我正在嘗試編寫一個prolog程序，它可以找到在二維數組中完全被b或w包圍的瓷磚。如何編寫程序來查找完全封閉的圖塊？

例如，給定一個像這樣的數據集：

[ 
    [b, w, +, +], 
    [w, +, w, b], 
    [+, w, b, +], 
    [+, +, +, b], 
]

這將返回一個包含另一個變量：

[ 
    [-, -, -, -], 
    [-, w, -, -], 
    [-, -, -, b], 
    [-, -, -, -], 
]

是，它取代了所有+這完全與包圍bb，對於那些被w包圍的人也是如此，並且用-代替了其他所有內容。

任何人都可以提供任何想法如何建立一個程序來做到這一點？

來源

2012-04-09 chustar

你有沒有在序言中做這個問題，或與一般的邏輯？如果前者，你會如何用另一種語言來做到這一點？如果是後者，你到目前爲止提出了什麼？ – 2012-04-09 01:21:18

我遇到了問題。在另一種語言中，我可能會使用強連通的組件算法之一，但我不知道如何將它應用於prolog（因爲我找不到數組索引和記住位置的方式） – chustar 2012-04-09 01:29:43

使用nth1/3來索引列表中的元素 – whd 2012-04-09 10:34:28

這可能會有所幫助：它將採用您給出的表示形式，並返回一個列表，其元素爲[ColumnIndex，RowIndex，Value]中的每一個。然後可以使用成員在特定的行/列中查找元素。

encodearray(A, AA) :- (A, 0, 0, AA). 
encodearray([], _, _, []). 
encodearray([[]|A], _, R, AA) :- R1 is R+1, encodeArray(A, 0, R1, AA). 
encodearray([[A|B]|X], C, R, [[C,R,A]|AA]) :- C1 is C+1, encodeArray([B|X], C1, R, AA).

來源

2012-04-09 02:11:53

謝謝。我將開始與此合作。 – chustar 2012-04-09 02:15:18

利用該REP/2謂詞

rep(L0, L1) :- 
    rep(b, L0, L1) ; 
    rep(w, L0, L1). 

rep(E, [E|Ps], [-|Rs]) :- 
    rep1(E, Ps, Rs). 
rep(E, [X|Ps], [-|Rs]) :- 
    E \= X, 
    rep(Ps, Rs). 

rep1(E, [+|Ps], [E|Rs]) :- 
    rep2(E, Ps, Rs). 

rep2(E, [+|Ps], [E|Rs]) :- 
    rep2(E, Ps, Rs). 
rep2(E, [E|Ps], [-|Rs]) :- 
    dash(Ps, Rs). 

dash([], []). 
dash([_|Ps], [-|Rs]) :- dash(Ps, Rs).

執行這種方式

?- rep([b,+,b,b],L). 
L = [-, b, -, -] ; 
false. 

?- rep([b,+,+,+,+,+,b,+,b],L). 
L = [-, b, b, b, b, b, -, -, -] . 

?- rep([w,+,+,+,+,+,w,+,b],L). 
L = [-, w, w, w, w, w, -, -, -] . 

?- rep([b,+,+,+,+,+,w,+,b],L). 
false. 

?- rep([b,+,+,+,+,+,+,b],L). 
L = [-, b, b, b, b, b, b, -] . 

?- rep([b,+,+,+,+,+,+,+,b],L). 
L = [-, b, b, b, b, b, b, b, -] . 

?- rep([b,+,+,w,+,+,w,+,b],L). 
L = [-, -, -, -, w, w, -, -, -] .

和換位謂詞啓用REP/2到列工作

transpose_col_row([], []). 
transpose_col_row([U], B) :- gen(U, B). 
transpose_col_row([H|T], R) :- transpose_col_row(T, TC), splash(H, TC, R). 

gen([H|T], [[H]|RT]) :- gen(T,RT). 
gen([], []). 

splash([], [], []). 
splash([H|T], [R|K], [[H|R]|U]) :- 
    splash(T,K,U).

你可以結合他們來解決你的問題問題。 HTH

來源

2012-04-09 09:07:20 CapelliC

如何編寫程序來查找完全封閉的圖塊？

回答

相關問題