新・Bランクレベルアップメニュー【全探索 4】ストラックアウト
【全探索 4】ストラックアウトコード (C++実装例参照)
reader.on('close', () => {
function next_permutation(A) {
const L = A.length - 1;
for (let i = L - 1; i >= 0; i--) {
if (A[i] < A[i + 1]) {
for (let j = L; j > i; j--) {
if (A[j] > A[i]) {
[A[i], A[j]] = [A[j], A[i]];
const len = (A.length - (i + 1)) >> 1;
for (let k = 0; k < len; k++) {
[A[i + 1 + k], A[L - k]] = [A[L - k], A[i + 1 + k]];
}
return true;
}
}
}
}
return false;
}
const s = [lines[0], lines[1], lines[2]].join(' ').split(' ').map(Number);
const b = [];
for (let i = 3; i < 12; i++) {
b.push(lines[i].split(' ').map(Number));
}
const panels = [];
let [ans, add] = [0, 0];
for (let i = 0; i < 9; i++) {
panels.push(i);
ans += s[i];
}
do {
const opened = Array(9).fill(false);
let tmp = 0;
for (let i = 0; i < 9; i++) {
let line = 0;
switch (panels[i]) {
case 0:
line += (opened[1] && opened[2] ? 1 : 0);
line += (opened[3] && opened[6] ? 1 : 0);
line += (opened[4] && opened[8] ? 1 : 0);
break;
case 1:
line += (opened[0] && opened[2] ? 1 : 0);
line += (opened[4] && opened[7] ? 1 : 0);
break;
case 2:
line += (opened[0] && opened[1] ? 1 : 0);
line += (opened[5] && opened[8] ? 1 : 0);
line += (opened[4] && opened[6] ? 1 : 0);
break;
case 3:
line += (opened[0] && opened[6] ? 1 : 0);
line += (opened[4] && opened[5] ? 1 : 0);
break;
case 4:
line += (opened[0] && opened[8] ? 1 : 0);
line += (opened[2] && opened[6] ? 1 : 0);
line += (opened[1] && opened[7] ? 1 : 0);
line += (opened[3] && opened[5] ? 1 : 0);
break;
case 5:
line += (opened[2] && opened[8] ? 1 : 0);
line += (opened[3] && opened[4] ? 1 : 0);
break;
case 6:
line += (opened[0] && opened[3] ? 1 : 0);
line += (opened[2] && opened[4] ? 1 : 0);
line += (opened[7] && opened[8] ? 1 : 0);
break;
case 7:
line += (opened[1] && opened[4] ? 1 : 0);
line += (opened[6] && opened[8] ? 1 : 0);
break;
case 8:
line += (opened[2] && opened[5] ? 1 : 0);
line += (opened[6] && opened[7] ? 1 : 0);
line += (opened[0] && opened[4] ? 1 : 0);
break;
}
if (0 < line) {
tmp += b[panels[i]][line - 1];
}
opened[panels[i]] = true;
}
add = Math.max(add, tmp);
} while (next_permutation(panels));
console.log(ans + add);
});
Ç++ の解答コード例を参照しました。
ストラックアウト の ルールがよく理解できなかったので…(^_^;)。
function next_permutation(A)
function next_permutation(A) {
const L = A.length - 1;
for (let i = L - 1; i >= 0; i--) {
if (A[i] < A[i + 1]) {
for (let j = L; j > i; j--) {
if (A[j] > A[i]) {
[A[i], A[j]] = [A[j], A[i]];
const len = (A.length - (i + 1)) >> 1;
for (let k = 0; k < len; k++) {
[A[i + 1 + k], A[L - k]] = [A[L - k], A[i + 1 + k]];
}
return true;
}
}
}
}
return false;
}引数として与えた 配列 の順列を取得しつつループ処理…。
コメント