UVa 154 - Recycling

 1  /*
 2  Problem link
 3  Type: Complete search
 4  Algorithm:
 5      For each row(city), calculate the sum of
 6      all the differences(score) from the other city:
 7      For example: r/P and r/G is 1 different
 8  
 9      Get the city with the minimum score!
10  */
11  #include <iostream>
12  #include <cstdio>
13  #include <cstring>
14  #include <cmath>
15  #include <cstdlib>
16  
17  using namespace std;
18  const int maxn = 110;
19  
20  string cities[maxn][5];
21  int n;
22  
23  bool readFile();
24  void selSort(int row);
25  int calculate(int row);
26  
27  int main()
28  {
29      while (readFile()) {
30          int minV = 2000000, result = 0;
31          for (int i = 1; i <= n; i++) {
32              int score = calculate(i);
33              if (score < minV) minV = score, result = i;
34          }
35          cout << result << endl;
36      }
37      return 0;
38  }
39  
40  bool readFile() {
41      string line;
42      cin >> line;
43      if (line[0] == '#' || cin.eof()) return false;
44      n = 1;
45  
46      while (true) {
47          if (line[0] == 'e' || line == "#") break;
48  
49          // Process string
50          for (int i = 0; i < (int)line.length(); i++)
51              if (line[i] == ',') line[i] = ' ';
52              line += ' ';
53          int indexBegin = 0, indexEnd = 0;
54          int cnt = 0;
55          while (indexEnd < (int)line.length()) {
56              indexEnd = line.find(" ", indexBegin);
57              if (indexEnd == -1) break;
58              cities[n][cnt++] = line.substr(indexBegin, indexEnd - indexBegin);
59              if (cnt == 5) {
60                  // We may sort the row for easier compare, this is optional
61                  selSort(n),
62                  n++, cnt = 0;
63              }
64              indexBegin = indexEnd+1;
65          }
66          cin >> line;
67      }
68      return true;
69  }
70  
71  // I just want to review selection sort algorithm here! :p
72  void selSort(int row) {
73      for (int i = 0; i < 5; i++) {
74          int j = i;
75          while (cities[row][j-1] > cities[row][j] && j>0) {
76              swap(cities[row][j-1], cities[row][j]);
77              j--;
78          }
79      }
80  }
81  
82  // Calculate the score for each row
83  int calculate(int row) {
84      int result = 0;
85      for (int i = 1; i <=n; i++)
86          if (i != row) {
87              for (int j = 0; j < 5; j++)
88                  // Now comparing gets easier with sorted array
89                  if (cities[row][j] != cities[i][j]) result++;
90          }
91      return result;
92  }