javascript - Pemprosesan tatasusunan dua dimensi, agak serupa dengan Solitaire

Question

var arr = [["A", "B"], ["C", "D"], ["E", "F"], ["G", "H"], ["C", "A"],["C","Q"] ["F", "D"], ["E", "G"],["H", "A"]];
var point = "A";//根据arr二维数组进行接龙，point这个是接龙的起点和终点
//要求输出:output_arr=[["A", "C"],["C", "D"],["D", "F"],["F", "E"],["E", "G"],["G", "H"],["H", "A"]]
//如上，起点和终点都为"A"
//用不到的元素舍弃了：["A", "B"]中"A"以后的"B"再接不下去，所以没用，同理["C","Q"]中的"Q"也接不下去，也不用了
//注意顺序:["C", "A"]，因为从"A"开始，所以这个元素变为["A","C"]

Saya tidak terlibat dalam bidang kerja ini Saya sendiri yang menulis program Apabila saya menghadapi masalah di atas, ia telah mengganggu saya selama beberapa hari

Answer 1

Sediakan idea penyelesaian tunggal.

Mula-mula cari tatasusunan yang elemen pertamanya ialah A, keluarkan dan namakannya tatasusunan calon

Kemudian pilih salah satu tatasusunan calon, dan kemudian tentukan tatasusunan semasa dan tatasusunan hasil untuk menyimpan hasil jumlah kepala dan ekor semasa, seperti [A,B] dan [[A,B], [B,C]] , Sudah tentu, tatasusunan semasa tidak perlu digunakan. Berikut adalah penjelasan yang mudah.

Kemudian gelung arr sehingga anda mengetahui tatasusunan yang huruf pertamanya ialah A, seperti [B,C]. Tatasusunan hasil ini boleh diruntuhkan ke dalam [A,C]. Maka sudah tentu kita perlu menyimpan [B, C] ke dalam tatasusunan hasil, dan padam [B, C] daripada arr.

Kemudian jika tatasusunan semasa dilipat ke panjang 0 selepas dikumpulkan, ini bermakna naga telah ditemui, dan hasilnya boleh dikeluarkan.

Tetapi jika ia tidak ditemui, ini bermakna [B, C] tidak mempunyai penyelesaian, maka tatasusunan hasil dan tatasusunan semasa akan dikembalikan ke peringkat sebelumnya, dan [B, C] tidak akan ditambahkan pada arr, kerana Ia tidak boleh menjadi salah satu jawapan. Kemudian teruskan mengulangi proses ini.

Penerangan titik imej ialah kita mendapati bahawa [A, B, B, C, C, D] tidak dapat mencari hasilnya, kembali ke [A, B, B, C], dan kemudian tidak dapat mencarinya, kemudian terus jatuh semula ke [ A,B]. Dan seterusnya.

Ketahui sehingga habis.

Jika terdapat pelbagai tafsiran, ia adalah penyelesaian yang sama. Terlalu banyak masalah.

Answer 2

Ini adalah latihan yang menyeluruh...
Idea yang boleh saya fikirkan ialah memilih dua hujung dan secara menyeluruh pergi ke tengah
Rekod setiap pasangan kemungkinan (perhatikan penguncian, anda tak boleh Repeated selection), asalkan hujung kemungkinan boleh disambung ok
Oleh kerana panjang keputusan tidak pasti, susunannya juga tidak pasti, yang menjadikannya lebih rumit.. .

Answer 3

Saya mengambil sedikit masa untuk menulis rekursi dan menggunakan logik pemangkasan Jika huruf hanya muncul sekali, maka pasangan huruf yang sepadan akan dialih keluar daripada data asal.

let map = {};   // 计算字母出现次数使用
let result = [];

// 计算字母出现次数
arr.forEach(item => {
    map[item[0]] ? map[item[0]]++ : (map[item[0]] = 1);
    map[item[1]] ? map[item[1]]++ : (map[item[1]] = 1);
});

// 淘汰包含出现小于1字母的数组, 避免无用递归
arr = arr.filter(item => {
    return (map[item[0]] > 1 && map[item[1]] > 1);
});

let dfs = (_point, _arr) => {
    for(let i = _arr.length; i--; ) {
        let item = _arr[i];
        if(item[0] === _point || item[1] === _point) {

            if(result.length === 0 && item[1] === _point) {
                [item[0], item[1]] = [item[1], item[0]];
            }

            let tempArr = Object.assign(_arr);  // 复制一个数组副本，方便回溯
            tempArr.splice(i, 1);   // 从临时数组中删去当前组，进一步递归

            if(item[1] === point || dfs(item[1], tempArr)) {
                // 如果找到答案，一层层往上返回
                // 不带下划线的point是全局的目标point
                result.unshift(item);
                return true;
            }
        }
    }
    return false;
};

if(dfs(point, arr)){
    console.log(result);
} else {
    console.log('no result');
}