/home/toolbox/public_html/solutions/103/10336/10336.cpp
1 #include <iostream>
2 #include <map>
3 #include <vector>
4
5 const int MAX = 1000;
6 std::map<char, int> languageFrequency;
7 std::vector<char> unique;
8 int height, width;
9 char world[MAX][MAX];
10 int val[MAX][MAX];
11
12 bool boundsCheck(int i, int j)
13 {
14 if (i < height && i >= 0 && j < width && j >= 0)
15 {
16 return true;
17 }
18 return false;
19 }
20
21 void printWorld()
22 {
23 for (int i = 0; i < height; i++)
24 {
25 for (int j = 0; j < width; j++)
26 {
27 std::cout << world[i][j];
28 }
29 std::cout << std::endl;
30 }
31 }
32
33 void printVal()
34 {
35 for (int i = 0; i < height; i++)
36 {
37 for (int j = 0; j < width; j++)
38 {
39 std::cout << val[i][j];
40 }
41 std::cout << std::endl;
42 }
43 }
44
45 void process()
46 {
47 std::vector<char>::iterator it = unique.begin();
48 std::vector<char>::iterator end = unique.end();
49 while (it != end)
50 {
51 int total = 0;
52 for (int i = 0; i < height; i++)
53 {
54 for (int j = 0; j < width; j++)
55 {
56 val[i][j] = 0;
57 }
58 }
59 bool found = true;
60 int count = 1;
61 while (found)
62 {
63 found = false;
64 bool flag = false;
65 for (int i = 0; i < height; i++)
66 {
67 for (int j = 0; j < width; j++)
68 {
69 if (world[i][j] == *it && val[i][j] == 0)
70 {
71 val[i][j] = count;
72 total++;
73 flag = true;
74 found = true;
75 break;
76 }
77 }
78 if (flag == true)
79 {
80 break;
81 }
82 }
83 bool changed = true;
84 while (changed)
85 {
86 changed = false;
87 for (int i = 0; i < height; i++)
88 {
89 for (int j = 0; j < width; j++)
90 {
91 //std::cerr << "(" << i << ", " << j << ")" << std::endl;
92 if (world[i][j] == *it && val[i][j] == count)
93 {
94 if (boundsCheck(i-1, j) && world[i-1][j] == *it && val[i-1][j] == 0)
95 {
96 val[i-1][j] = count;
97 changed = true;
98 }
99 if (boundsCheck(i+1, j) && world[i+1][j] == *it && val[i+1][j] == 0)
100 {
101 val[i+1][j] = count;
102 changed = true;
103 }
104 if (boundsCheck(i, j-1) && world[i][j-1] == *it && val[i][j-1] == 0)
105 {
106 val[i][j-1] = count;
107 changed = true;
108 }
109 if (boundsCheck(i, j+1) && world[i][j+1] == *it && val[i][j+1] == 0)
110 {
111 val[i][j+1] = count;
112 changed = true;
113 }
114 }
115 }
116 }
117 }
118 ++count;
119 }
120 languageFrequency.insert(std::pair<char, int>(*it, total));
121 ++it;
122 }
123 }
124
125 int main()
126 {
127 int cases;
128 int currentCase = 1;
129 std::cin >> cases;
130 while (cases > 0)
131 {
132 unique.clear();
133 std::cin >> height;
134 std::cin >> width;
135 for (int i = 0; i < height; i++)
136 {
137 for (int j = 0; j < width; j++)
138 {
139 std::cin >> world[i][j];
140 //Check to see if in unique
141 std::vector<char>::iterator it = unique.begin();
142 std::vector<char>::iterator end = unique.end();
143 bool found = false;
144 while (it != end)
145 {
146 if (*it == world[i][j])
147 {
148 found = true;
149 }
150 ++it;
151 }
152 if (found == false)
153 {
154 unique.push_back(world[i][j]);
155 }
156 }
157 }
158 process();
159 //Does not work
160 std::map<char, int>::iterator i = languageFrequency.begin();
161 std::map<char, int>::iterator iend = languageFrequency.end();
162 std::vector<std::pair<char, int > > sortedPair;
163 char min1 = i->first;
164 int min2 = i->second;
165 while (i != iend)
166 {
167 min1 = i->first;
168 min2 = i->second;
169 std::map<char, int>::iterator j = i;
170 std::map<char, int>::iterator jend = languageFrequency.end();
171 while (j != jend)
172 {
173 if (j->first < min1)
174 {
175 min1 = j->first;
176 min2 = j->second;
177 }
178 j++;
179 }
180 sortedPair.push_back(std::pair<char, int>(min1, min2));
181 i++;
182 }
183 std::vector<std::pair<char, int > > answer;
184 std::vector<std::pair<char, int> >::iterator maxIt;
185 char max1;
186 int max2;
187 std::vector<std::pair<char, int> >::size_type totalAltered = 0;
188 while (totalAltered != sortedPair.size())
189 {
190 for (std::vector<std::pair<char, int> >::iterator x = sortedPair.begin(); x!= sortedPair.end(); x++)
191 {
192 max1 = '\0';
193 max2 = -1;
194 for (std::vector<std::pair<char, int> >::iterator y = sortedPair.begin(); y!= sortedPair.end(); y++)
195 {
196 if (y->second > max2)
197 {
198 max1 = y->first;
199 max2 = y->second;
200 maxIt = y;
201 }
202 }
203 maxIt->second = -1;
204 answer.push_back(std::pair<char, int>(max1, max2));
205 totalAltered++;
206
207 }
208 }
209 std::cout << "World #" << currentCase << std::endl;
210 for (std::vector<std::pair<char, int> >::size_type x= 0; x<sortedPair.size(); x++)
211 {
212 std::cout << answer[x].first << ": " << answer[x].second << std::endl;
213 ++i;
214 }
215 languageFrequency.clear();
216 currentCase++;
217 cases--;
218 }
219 return 0;
220 }
221