fork download
copy 
  1. #include<bits/stdc++.h> 
  2. using namespace std;
  3.  
  4. struct itemq 
  5. { 
  6.     string w; 
  7.     int l; 
  8. };
  9. bool adj(string& a, string& b) 
  10. { 
  11.  
  12.     int n = a.length();
  13.     int c = 0; 
  14.  
  15.     for (int i = 0; i < n; i++) 
  16.     { 
  17.         if (a[i] != b[i]) 
  18.             c++;
  19.         if (c > 1) 
  20.             return false; 
  21.     }
  22.     if(c==1)
  23.         return true;
  24.     else
  25.         return false;
  26.     //return c == 1 ? true : false; 
  27. } 
  28. int ans(string& start, string& end, set<string> &D) 
  29. { 
  30.     if(start==end)
  31.         return 0;
  32.     queue<itemq> Q; 
  33.     itemq item = {start, 1};
  34.     Q.push(item); 
  35.  
  36.     while (!Q.empty()) 
  37.     {
  38.         itemq curr = Q.front(); 
  39.         Q.pop();
  40.         set<string>::iterator it;
  41.         for (it = D.begin(); it != D.end(); it++) 
  42.         { 
  43.             string temp = *it; 
  44.             if (adj(curr.w, temp)) 
  45.             { 
  46.                 item.w = temp; 
  47.                 item.l = curr.l + 1; 
  48.                 Q.push(item); 
  49.                 D.erase(temp); 
  50.  
  51.                 if (temp == end) 
  52.                   return item.l; 
  53.             } 
  54.         } 
  55.     }
  56.     return -1; 
  57. } 
  58. int main(void) 
  59. { 
  60.     string s;
  61.     set<string> D;
  62.     cin>>s;
  63.     while(s!="END")
  64.     {
  65.         D.insert(s);
  66.         cin>>s;
  67.     }
  68.     string start;
  69.     cin>>start;
  70.     string end;
  71.     cin>>end; 
  72.     cout << ans(start, end, D)<<endl;  
  73.     return 0;  
  74. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
cool
pool

END
cool pool
stdout
copy 
2
https://ideone.com/M2OIPS
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!