fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const int MX = 205;
  6.  
  7. vector <int> v[MX];
  8. int vist[MX], mn;
  9.  
  10. void init()
  11. {
  12.     for(int i=0; i<MX; i++)
  13.     {
  14.         v[i].clear();
  15.     }
  16. }
  17.  
  18. void dfs(int src, int des, int cur)
  19. {
  20.     if(cur >= mn)
  21.         return;
  22.     if(src == des)
  23.     {
  24.         mn = min(cur, mn);
  25.         return;
  26.     }
  27.     vist[src] = 1;
  28.     int i, x;
  29.     for(i=0; i<v[src].size(); i++)
  30.     {
  31.         x = v[src][i];
  32.         if( !vist[x] )
  33.         {
  34.             dfs(x, des, cur+1);
  35.         }
  36.     }
  37.     vist[src] = 0;
  38. }
  39.  
  40. int compare(string a, string b)
  41. {
  42.     int cnt=0, i, l = a.size();
  43.     for(i=0; i<l; i++)
  44.     {
  45.         if(a[i] == b[i])
  46.             cnt++;
  47.     }
  48.     if(cnt >= l-1)
  49.         return 0;
  50.     return 1;
  51. }
  52.  
  53. int main()
  54. {
  55.     string a, b, s;
  56.     int c, t, i, f=0,j, k;
  57.     scanf("%d",  &t);
  58.     cin.ignore();
  59.     while(t--)
  60.     {
  61.         init();
  62.         vector <string> mp[11];
  63.         map <string, int> mps;
  64.         c=0;
  65.         while(cin >> a)
  66.         {
  67.             if( a == "*" )
  68.                 break;
  69.             mp[a.size()].push_back(a);
  70.             mps[a] = c;
  71.             c++;
  72.         }
  73.         for(i=1; i<=10; i++)
  74.         {
  75.             for(j=0; j<mp[i].size(); j++)
  76.             {
  77.                 for(k=0; k<mp[i].size(); k++)
  78.                 {
  79.                     if(j != k)
  80.                     {
  81.                         if( !compare(mp[i][j], mp[i][k]) )
  82.                         {
  83.                             v[mps[mp[i][j]]].push_back(mps[mp[i][k]]);
  84.                             v[mps[mp[i][k]]].push_back(mps[mp[i][j]]);
  85.                         }
  86.                     }
  87.                 }
  88.             }
  89.         }
  90.         cin.ignore();
  91.         if(f)
  92.             puts("");
  93.         f=1;
  94.         while(getline(cin, s) && s.size() > 0)
  95.         {
  96.             istringstream ss(s);
  97.             string x;
  98.             i=0;
  99.             while(ss >> x)
  100.             {
  101.                 if(i == 0)
  102.                     a = x;
  103.                 else
  104.                     b = x;
  105.                 i++;
  106.             }
  107.             memset(vist, 0, sizeof vist);
  108.             mn = mp[a.size()].size();
  109.             dfs(mps[a], mps[b], 0);
  110.             cout << a << " " <<  b << " " << mn << endl;
  111.         }
  112.     }
  113.     return 0;
  114. }
  115.  
Success #stdin #stdout 0s 15256KB
comments (?)
stdin
copy 
2

dip
lip
mad
map
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod

dip
lip
mad
map
mapl
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice slick
may mad
map map
stdout
copy 
spice stock 4
may pod 3

spice slick 2
may mad 1
map map 0
https://ideone.com/FlHVmI
language:
C++14 (gcc 8.3)
created:
7 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!