每选两张牌,四川省的应用都会判定“这两张牌能不能用转弯不超过两次的线连上”。用提示寻找能消除的对时,也是对所有的对使用同样的判定。这篇文章用程序来介绍它的原理。
想法:按转弯的次数逐步扩大
线沿着竖直或水平方向笔直前进,偶尔转弯。所以,从第一张牌开始,像下面这样查找。
- 转弯0次:从第一张牌向上下左右,沿着空格笔直前进。到达第二张牌,就是能连上。
- 转弯1次:从第1步能走到的每个格子出发,改变方向,再笔直前进。
- 转弯2次:从第2步能走到的每个格子出发,改变方向,再笔直前进一次。
如果到第3步还没有到达第二张牌,就说明转弯两次以内连不上。笔直前进,直到撞上牌或者走出牌桌为止。
牌桌外侧的处理
线也可以经过牌桌外侧的一圈格子。在程序里,只要使用在牌桌周围多加了一圈空格的牌桌,外侧就可以当作普通的空格来处理。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用来记住以同一个方向到过同一个格子,避免重复查找。
这个程序,会一直查到第二次转弯之后笔直前进的前方,看能不能到达第二张牌。牌的上面不能通过,所以撞上就停(只有第二张牌,到达的那一刻就判定)。
与应用的核对
我们把这个程序和应用使用的找线方法(也用在了网站文章的图里的计算)做了比较。用和应用相同的方法生成了300局48张牌的牌桌,包括消到一半的牌桌在内,让它对随机选出的5044对牌进行判定,“能连上、连不上”的答案全部一致。
应用在能连上时,会在画面上画出线,所以不仅要知道能不能连上,还要记住拐角的位置。线有好几种走法时,会选转弯少的线,转弯次数相同的话就选短的线来画。
要找出所有能消除的对
像提示那样寻找能消除的对时,对每一对相同图案的两张牌,都用这个程序来判定。48张的牌桌上,相同图案的组合有72对,所以最多判定72次就够了。开局能消除的对数在开局能消除几对?里数过了。
