C++


  • 0
    J

    This would be the C++ Solution to the problem.

    #include <map>
    #include <set>
    #include <list>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <limits>
    #include <vector>
    #include <climits>
    #include <cstring>
    #include <cstdlib>
    #include <fstream>
    #include <numeric>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <unordered_map>

    using namespace std;

    int main() {
    ofstream fout(getenv("OUTPUT_PATH"));
    int res;
    string _start;
    getline(cin, _start);

    string _end;
    getline(cin, _end);
    
    
    int _bank_size = 0;
    cin >> _bank_size;
    cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n'); 
    vector<string> _bank;
    string _bank_item;
    for(int _bank_i=0; _bank_i<_bank_size; _bank_i++) {
        getline(cin, _bank_item);
        _bank.push_back(_bank_item);
    }
    
    res = findMutationDistance(_start, _end, _bank);
    fout << res << endl;
    
    fout.close();
    return 0;
    

    }

    bool connected(const string a, const string b ){
    bool diff = false;
    for(int i=0; i<8; ++i){
    if(a[i] != b[i] && diff){
    return false;
    }
    else if (a[i] != b[i]){
    diff = true;
    }
    }
    return true;
    }

    int findMutationDistance(string start, string end, vector < string > bank) {
    list< vector<int> > adjL;
    int bs = bank.size();
    int dim = bs + 2;
    vector< vector<int> > G(dim);
    for(int s=0; s<bs; ++s){
    if(connected(start, bank[s])){
    G[0].push_back(s+1);
    }
    }
    if(connected(start, end)){
    return 1;
    }
    for(int s=0; s<bs; ++s){
    if(connected(end, bank[s])){
    G[dim-1].push_back(s+1);
    }
    }
    for(int i=0; i<bs; ++i){

       if(connected(start, bank[i])){
       	G[i+1].push_back(0);
       }
        for (int j=0; j<i; ++j){
            if(connected(bank[i], bank[j])){
                G[i+1].push_back(j+1);
            }
        } 
        for(int k=i+1; k<bs; ++k){
          if(connected(bank[i], bank[k])){
                G[i+1].push_back(k+1);
            }  
        } 
        if(connected(end, bank[i])){
       	G[i+1].push_back(dim-1);
       }
    }
    

    for(int x = 0; x<G[0].size(); ++x){
    cout<<G[dim-2][x]<<endl;
    }
    return 2;
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.