uva 140 - Bandwidth

/*

Problem link

Type: Ad hoc

Algorithm: Complete search

*/ 

  1  #include <iostream>
  2  #include <cstdio>
  3  #include <cstring>
  4  #include <cmath>
  5  #include <cstdlib>
  6  #include <map>
  7  #include <vector>
  8  #include <algorithm>
  9  using namespace std;
 10  
 11  const int maxn = 10;
 12  
 13  map<char,int> nodes;
 14  map<int,char> NodesName;
 15  bool a[maxn][maxn];
 16  bool fre[maxn];
 17  int pos[maxn];
 18  char ans[maxn],anstmp[maxn];
 19  int n;
 20  
 21  bool ReadInput();
 22  void attempt(int i, int& result);
 23  bool cmp(char ch1[], char ch2[]);
 24  
 25  int main()
 26  {
 27      while (ReadInput())
 28      {
 29          int result = 1000;
 30          for (int i=1; i<=n; i++) fre[i] = 1;
 31          attempt(1,result);
 32          for (int i=1; i<=n; i++) cout << ans[i] << " ";
 33          cout << "-> " << result << endl;
 34      }
 35      return 0;
 36  }
 37  
 38  bool ReadInput()
 39  {
 40      string line;
 41      cin >> line;
 42      if (line=="#") return(false);
 43      for (int i=0; i<maxn; i++)
 44          for (int j=0; j<maxn; j++) a[i][j] = false;
 45      unsigned int index = 0;
 46      for (char i = 'A'; i<='Z'; i++) nodes[i] = 0;
 47      char i,j;
 48      n = 0;
 49      while (index<line.length())
 50      {
 51          i = line[index];
 52          if (nodes[i]==0)
 53          {
 54              nodes[i] = ++n;
 55              NodesName[nodes[i]] = i;
 56          }
 57          index+=2;
 58          while (line[index]!=';' && index<line.length())
 59          {
 60              j = line[index];
 61              if (nodes[j]==0)
 62              {
 63                  nodes[j] = ++n;
 64                  NodesName[nodes[j]] = j;
 65              }
 66              a[nodes[i]][nodes[j]] = true;
 67              a[nodes[j]][nodes[i]] = true;
 68              index++;
 69          }
 70          index++;
 71      }
 72      return(true);
 73  }
 74  
 75  void attempt(int i, int& result)
 76  {
 77      if (i==n+1)
 78      {
 79          int maxdist = 0;
 80          for (int j=1; j<=n; j++)
 81              for (int k=1; k<=n; k++)
 82                  if (a[j][k] && abs(pos[j]-pos[k])>maxdist) maxdist = abs(pos[j]-pos[k]);
 83  
 84          if (maxdist<result)
 85          {
 86              result = maxdist;
 87              for (int j=1; j<=n; j++) ans[pos[j]] = NodesName[j];
 88          }
 89          else if (maxdist==result)
 90          {
 91              for (int j=1; j<=n; j++) anstmp[pos[j]] = NodesName[j];
 92              if (cmp(anstmp,ans))
 93                  for (int j=1; j<=n; j++) ans[j] = anstmp[j];
 94          }
 95          return;
 96      }
 97  
 98      for (int j=1; j<=n; j++)
 99          if (fre[j])
100          {
101              pos[j] = i;
102              fre[j] = false;
103              attempt(i+1,result);
104              fre[j] =true;
105          }
106  }
107  
108  bool cmp(char ch1[], char ch2[])
109  {
110      for (int i=1; i<=n; i++)
111          if (ch1[i]<ch2[i]) return(true);
112          else if (ch1[i]>ch2[i]) return(false);
113      return(false);
114  }