javascript - Traitement de tableaux bidimensionnels, un peu similaire au 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"]

Je ne suis pas engagé dans ce domaine de travail. J'écris moi-même des programmes Lorsque j'ai rencontré le problème ci-dessus, cela me dérange depuis plusieurs jours. S'il vous plaît, aidez-moi.

Answer 1

Fournissez une idée de solution unique.

Trouvez d'abord le tableau dont le premier élément est A, retirez-le et nommez-le tableau candidat

Sélectionnez ensuite l'un des tableaux candidats, puis définissez un tableau actuel et un tableau de résultats pour stocker les résultats actuels de la somme de tête et de queue, tels que [A, B] et [[A, B], [B, C]] , Bien sûr, le tableau actuel n'a pas besoin d'être utilisé. Voici une explication pratique.

Ensuite, bouclez arr jusqu'à ce que vous connaissiez le tableau dont la première lettre est A, tel que [B,C]. Ce tableau de résultats peut être réduit en [A,C]. Ensuite, bien sûr, nous devons enregistrer [B, C] dans le tableau de résultats et supprimer [B, C] de l'arr.

Ensuite, si le tableau actuel est plié à la longueur 0 après le regroupement, cela signifie qu'un dragon a été trouvé et le résultat peut être affiché.

Mais s'il est introuvable, cela signifie que [B, C] n'a pas de solution, alors le tableau résultat et le tableau actuel seront renvoyés à l'étape précédente, et [B, C] ne sera plus ajouté à arr, parce que cela ne peut pas être l'une des réponses. Continuez ensuite à répéter ce processus.

La description du point d'image est que nous constatons que [A, B, B, C, C, D] ne peut pas trouver le résultat, revenons à [A, B, B, C], puis ne pouvons pas le trouver, alors continuez à revenir à [ A, B ]. Et ainsi de suite.

Découvrez-le jusqu'à la fin.

S'il y a plusieurs interprétations, c'est exactement la même solution. Trop de problèmes.

Answer 2

C'est un exercice exhaustif...
L'idée à laquelle je peux penser est de sélectionner deux extrémités et de rechercher de manière exhaustive vers le milieu.
Enregistrez chaque paire de possibilités (notez qu'elles sont verrouillées et ne peuvent pas être sélectionnées à plusieurs reprises), et la fin des possibilités peuvent être Si vous pouvez l'attraper, ce n'est pas grave
Comme la longueur des résultats est incertaine, et l'ordre est également incertain, c'est beaucoup plus compliqué...

Answer 3

Il m'a fallu un certain temps pour écrire une récursion et utiliser une logique d'élagage. Si une lettre n'apparaît qu'une seule fois, alors la paire de lettres correspondante sera supprimée des données d'origine.

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');
}