四川省(兩次轉彎消除)的 App,每次選兩張牌,都會判定「這兩張牌能不能用轉彎兩次以內的線連起來」。用提示尋找能消除的對時,也是對所有的對使用相同的判定。這篇文章要用程式來介紹這個原理。
想法:依轉彎次數逐步擴大
線是沿著直線或橫線筆直前進,偶爾轉彎。所以,從第 1 張牌開始,這樣依序檢查。
- 轉彎 0 次:從第 1 張牌往上下左右,沿著空格筆直前進。如果走到第 2 張牌,就連得起來。
- 轉彎 1 次:從 1 走得到的每一格,換個方向,再次筆直前進。
- 轉彎 2 次:從 2 走得到的每一格,換個方向,再筆直前進一次。
如果到第 3 次為止都沒走到第 2 張牌,就表示用兩次以內的轉彎連不起來。筆直前進,是走到撞上牌或是走出牌桌外為止。
牌桌外側的處理
線也可以通過牌桌外側的一圈空格。在程式裡,只要使用在牌桌四周多加一圈空格的牌桌,外側就能當成普通的空格來處理。6 列×8 行的牌桌,就用 8 列×10 行的牌桌來檢查。
這張圖上方列兩端的五條,通過上方外側的空格,轉彎 2 次就連起來了。
程式
用 JavaScript 寫,會像下面這樣。
// board[r][c] 是牌的名稱,空格是 null。牌桌四周各多加了一圈空格的外框。
function canConnect(board, from, to) {
const rows = board.length;
const cols = board[0].length;
const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
// 目前所在的格子,以及最後前進的方向(一開始是 -1)
let frontier = [[from[0], from[1], -1]];
const seen = new Set();
for (let turn = 0; turn <= 2; turn++) {
const next = [];
for (const [r0, c0, dir] of frontier) {
for (let d = 0; d < 4; d++) {
if (d === dir) continue;
let r = r0;
let c = c0;
while (true) {
r += steps[d][0];
c += steps[d][1];
if (r < 0 || c < 0 || r >= rows || c >= cols) break;
if (r === to[0] && c === to[1]) return true;
if (board[r][c] !== null) break;
const key = r + ',' + c + ',' + d;
if (!seen.has(key)) {
seen.add(key);
next.push([r, c, d]);
}
}
}
}
frontier = next;
}
return false;
} board是四周加了一圈空格外框的牌桌。有牌的格子放牌的名稱,空格放null。from和to是兩張牌的[列, 行](加了外框之後的牌桌上的位置)。frontier是以目前的轉彎次數能走到的格子,以及走到那裡時的方向清單。- 往同一個方向繼續筆直前進,在前一輪已經檢查過了,所以跳過(
d === dir)。 seen是用來記住同一格已經從同一個方向到達過,避免重複檢查。
這個程式,會連第 2 次轉彎之後筆直前進所到之處,是否走到第 2 張牌都檢查。牌的上面不能通過,所以撞上就停下來(只有第 2 張牌,是在走到的當下判定)。
與 App 對照
我們把這個程式,拿來和 App 的找線方式(本站文章的圖也是用這個計算)比較。用和 App 相同的方式做出 300 局 48 張的牌桌,包括消到一半的牌桌在內,對隨機選的 5044 組牌做判定,結果連得起來、連不起來的答案全部一致。
App 在連得起來時會在畫面上畫線,所以不只記住能不能連起來,連轉角的位置也會記住。線有很多種畫法時,會選轉彎少的線,轉彎次數相同就選比較短的線來畫。
要找出所有能消除的對
像提示這樣尋找能消除的對時,是針對每一組相同圖案的兩張牌,用這個程式來判定。48 張的牌桌,相同圖案的組合有 72 組,所以最多判定 72 次就夠了。一開始能消除的對數,在一開始能消除幾對?裡數過了。
