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. int min(int x, int y, int z) 
  10. { 
  11.    return min(min(x, y), z); 
  12. } 
  13.  
  14. int lev(string str1 , string str2 , int m ,int n) 
  15. { 
  16.     if (m == 0) 
  17.     	return n; 
  18.     if (n == 0) 
  19.     	return m; 
  20.     if (str1[m-1] == str2[n-1]) 
  21.         return lev(str1, str2, m-1, n-1); 
  22.     return 1 + min ( lev(str1,  str2, m, n-1),    // Insert 
  23.                      lev(str1,  str2, m-1, n),   // Remove 
  24.                      lev(str1,  str2, m-1, n-1) // Replace 
  25.                    ); 
  26. } 
  27. bool adj(string& a, string& b) 
  28. { 
  29.     if(lev(a,b,a.size(),b.size())==1)
  30.         return true;
  31.     else
  32.         return false;
  33. } 
  34. int ans(string& start, string& end, set<string> &D) 
  35. { 
  36.     if(start==end)
  37.         return 1;
  38.     queue<itemq> Q; 
  39.     itemq item = {start, 1};
  40.     Q.push(item); 
  41. 	//D.erase(start);
  42.     while (!Q.empty()) 
  43.     {
  44.         itemq curr = Q.front(); 
  45.         Q.pop();
  46.         set<string>::iterator it;
  47.         for (it = D.begin(); it != D.end(); it++) 
  48.         { 
  49.         	cout<<curr.w<<" "<<*it<<endl;
  50.             string temp = *it; 
  51.             if (adj(curr.w, temp)) 
  52.             { 
  53.  
  54.                 item.w = temp; 
  55.                 item.l = curr.l + 1; 
  56.                 Q.push(item);
  57.                 D.erase(temp); 
  58.                 if (temp == end) 
  59.                   return item.l; 
  60.             } 
  61.         } 
  62.     }
  63.     return -1; 
  64. } 
  65. int main(void) 
  66. { 
  67.     string s;
  68.     set<string> D;
  69.     cin>>s;
  70.     while(s!="END")
  71.     {
  72.         D.insert(s);
  73.         cin>>s;
  74.     }
  75.     string start;
  76.     cin>>start;
  77.     string end;
  78.     cin>>end;
  79.     set<string>::iterator it;
  80.     for (it = D.begin(); it != D.end(); it++) 
  81.     	cout<<*it<<endl;
  82.     int cou = ans(start, end, D);
  83.     cout << cou <<endl;  
  84.     return 0;  
  85. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
cat
mat
hat
nat
ham
mate
END
cat mate
stdout
copy 
cat
ham
hat
mat
mate
nat
cat cat
cat ham
cat hat
cat mate
cat nat
cat mate
hat cat
hat ham
hat mat
hat mate
nat mate
cat mate
ham mate
mat mate
4
https://ideone.com/buTdSE
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!