Code: Select all
A:FB;B:GC;D:GC;F:AGH;E:HD
A:FB;B:GC;D:GC;F:AGH;E:H
A:B;B:C;C:D;D:E;E:F;F:G;G:H
A:B;B:C;C:D;D:E;E:F;F:G;G:H;H:A
A:B;B:CE;C:D;D:E;E:F;F:G;G:H;H:A
A:B;B:CE;CG:D;D:E;E:F;F:G;G:H;H:A <--Wrong Input, sorry
A:B;B:CE;C:DG;D:E;E:F;F:G;G:H;H:A
A:BCDEFGH;B:ACDEFGH;C:ABDEFGH;D:ABCEFGH;E:ABCDFGH;F:ABCDEGH;G:ABCDEFH;H:ABCDEFG
#Code: Select all
A B C F G D H E -> 3
C D B G A F E H -> 2
A B C D E F G H -> 1
A B H C G D F E -> 2
C D B E A F H G -> 2
A B C E D F G H -> 2
A B H C E G D F -> 3
A B C D E F G H -> 7Code: Select all
A B C F G D H E -> 3
C D B G A F E H -> 2
A B C D E F G H -> 1
A B H C G D F E -> 2
C D B E A F H G -> 2
A B C H E D G F -> 3
A B H C E G D F -> 3
A B C D E F G H -> 7
Code: Select all
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<string>
#define MAX 1000001
using namespace std;
string i2s(int n)
{ stringstream ss;
ss<<n;
return ss.str();
}
int s2i(string h)
{ stringstream ss;
ss<<h;
int n;
ss>>n;
return n;
}
int main()
{ string h1="";
while(getline(cin,h1))
{ if(h1=="#")
{ break;
}
set<char> s;s.clear();
for(int i=0;i<h1.size();i++)
{ if(h1[i]!=';' && h1[i]!=':')
{ s.insert(h1[i]);
}
}
vector<char> re;re.clear();
for(set<char>::iterator i1=s.begin();i1!=s.end();i1++)
{ re.push_back(*i1);
}
int arr[s.size()][s.size()];memset(arr,0,sizeof(arr));
int cnt=0;
// formation of the graph for connectivity
for(set<char>::iterator i1=s.begin();i1!=s.end();i1++)
{ string k1="";k1+=(*i1);k1+=":";
int pos=h1.find(k1);
if(pos==string::npos)
{ cnt++;continue;
}
pos+=2;
while(h1[pos]!=';' && pos<h1.size())
{ int pos1=find(re.begin(),re.end(),h1[pos])-re.begin();
arr[cnt][pos1]=1;arr[pos1][cnt]=1;
pos++;
}
cnt++;
}
// formation of string having all symbols neighbours
string h="";
for(int i=0;i<s.size();i++)
{ h+=re[i];h+=":";
for(int j=0;j<s.size();j++)
{ if(arr[i][j]==1){h+=re[j];}
}
h+=";";
}
h.erase(h.size()-1);
vector<char> save;save.clear();
int min3=1000000000;
// checking all the premutations
do
{ //case of bandwidth of ordering
int max1=-1;
for(int i=0;i<re.size();i++)
{ string k1="";k1+=re[i];k1+=":";
int pos=h.find(k1);pos+=2;int max2=-1;
while(h[pos]!=';' && pos<h.size())
{ int pos1=find(re.begin(),re.end(),h[pos])-re.begin();
int val=abs(pos1-i);
max2=max(max2,val);
pos++;
}
max1=max(max1,max2);
}
if(min3>max1)
{ min3=max1;
save.clear();
for(int i=0;i<re.size();i++){save.push_back(re[i]);}
}
}while(next_permutation(re.begin(),re.end()));
for(int i=0;i<save.size();i++)
{ cout<<save[i]<<" ";
}
cout<<"-> "<<min3<<endl;
}
system("pause");
}