1using System;
2using System.Collections.Generic;
3
4public class GeneticMutation {
5    public int MinMutation(string startGene, string endGene, string[] bank) {
6        var geneBank = new HashSet<string>(bank);
7        if (!geneBank.Contains(endGene)) return -1;
8
9        var choices = new char[] {'A', 'C', 'G', 'T'};
10        var queue = new Queue<(string gene, int steps)>();
11        queue.Enqueue((startGene, 0));
12
13        while (queue.Count > 0) {
            var (gene, steps) = queue.Dequeue();

            if (gene == endGene) return steps;

            for (int i = 0; i < gene.Length; i++) {
                var geneArray = gene.ToCharArray();
                char original = gene[i];

                foreach (var choice in choices) {
                    if (choice == original) continue;
                    geneArray[i] = choice;
                    string newGene = new string(geneArray);

                    if (geneBank.Contains(newGene)) {
                        geneBank.Remove(newGene);
                        queue.Enqueue((newGene, steps + 1));
                    }
                }
                geneArray[i] = original;
            }
        }
        return -1;
    }

    public static void Main() {
        var gm = new GeneticMutation();
        string startGene = "AACCGGTT";
        string endGene = "AAACGGTA";
        string[] bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        Console.WriteLine(gm.MinMutation(startGene, endGene, bank));
    }
}

1#include <iostream>
2#include <unordered_set>
3#include <vector>
using namespace std;

int minMutation(string startGene, string endGene, vector<string>& bank) {
    unordered_set<string> geneBank(begin(bank), end(bank));
    if (!geneBank.count(endGene)) return -1;

    unordered_set<string> forward = {startGene};
    unordered_set<string> backward = {endGene};

    int steps = 0;
    vector<char> choices = {'A', 'C', 'G', 'T'};

    while (!forward.empty() && !backward.empty()) {
        if (forward.size() > backward.size())
            swap(forward, backward);

        unordered_set<string> nextLevel;

        for (const string& gene : forward) {
            string currentGene = gene;
            
            for (int i = 0; i < currentGene.size(); ++i) {
                char original = currentGene[i];
                for (char c : choices) {
                    currentGene[i] = c;
                    if (backward.find(currentGene) != backward.end())
                        return steps + 1;

                    if (geneBank.find(currentGene) != geneBank.end()) {
                        nextLevel.insert(currentGene);
                        geneBank.erase(currentGene);
                    }
                }
                currentGene[i] = original;
            }
        }

        swap(forward, nextLevel);
        ++steps;
    }

    return -1;
}

int main() {
    vector<string> bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    cout << minMutation("AACCGGTT", "AAACGGTA", bank) << endl;
    return 0;
}