/home/toolbox/public_html/solutions/103/10336/judged.c
1 #include <stdio.h>
2 #include <strings.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdlib.h>
7
8 /*
9 * Author: Unknown
10 * Date: 2005-02-01
11 * Purpose: Contest practice
12 * Problem: 10336 - Rank the Languages <http://isaac.lsu.edu/udv/v103/10336.html>
13 */
14
15 #define TRUE (1 == 1)
16 #define FALSE (1 != 1)
17
18 #define VISITED '0'
19
20 #define DEBUG if (FALSE)
21 #define MAXSIZE 1000
22 #define ALPHASIZE 26
23 #define AM(a) (a-'a')
24
25 typedef struct
26 {
27 char letter;
28 char num;
29 } lang;
30
31 int w, h;
32 char arr[MAXSIZE][MAXSIZE];
33 int languages[ALPHASIZE];
34 lang letters [ALPHASIZE];
35 /*char letters [ALPHASIZE];*/
36
37 int numberOfTimes;
38
39 void langInit ()
40 {
41 int x;
42 for ( x = 0; x < ALPHASIZE; x ++)
43 {
44 /*Count array init*/
45 languages[x] = 0;
46 } /*Count array init*/
47 }
48 void init()
49 {
50 /* FUNCTION init */
51 scanf("%d ", &numberOfTimes);
52 } /* FUNCTION init */
53
54 void langDump ()
55 {
56 /* FUNCTION langDump */
57 int x;
58 printf("\n");
59 for ( x = 0; ALPHASIZE > x; x ++)
60 {
61 printf("%d ", languages[x]);
62 }
63 printf("\n");
64 } /* FUNCTION langDump */
65
66 void dump()
67 {
68 /* FUNCTION dump */
69 int x, y;
70 printf(" %d by %d\n", w, h);
71 for (y = 0; h > y; y ++)
72 {
73 for (x = 0; w > x; x ++)
74 {
75 printf("%c ", arr[x][y]);
76 }
77 printf("\n");
78 }
79 } /* FUNCTION dump */
80
81 void getInput()
82 {
83 /* FUNCTION getInput */
84 int x, y;
85
86 scanf("%d %d ", &h, &w);
87
88 if ((MAXSIZE < w) || (MAXSIZE < h))
89 {
90 fprintf(stderr, "overflow\n");
91 exit(1);
92 }
93
94 for (y = 0; y < h; y ++)
95 {
96 for (x = 0; w > x; x ++)
97 {
98 scanf(" %c ", &(arr[x][y]));
99 }
100 }
101
102 } /* FUNCTION getInput */
103
104
105 void visitRecurse (int x, int y, char c)
106 {
107 /* FUNCTION visitRecurse */
108 if (0 <= x && 0 <= y && w > x && h > y && arr[x][y] == c)
109 {
110 c = arr[x][y];
111 arr[x][y] = VISITED;
112 visitRecurse(x - 1, y, c);
113 visitRecurse(x, y - 1, c);
114 visitRecurse(x + 1, y, c);
115 visitRecurse(x, y + 1, c);
116 }
117 } /* FUNCTION visitRecurse */
118
119 void visit (int x, int y)
120 {
121 /* FUNCTION visit */
122 char temp;
123 temp = arr[x][y];
124 languages[AM(temp)]++;
125 arr[x][y] = VISITED;
126 visitRecurse(x - 1, y, temp);
127 visitRecurse(x, y - 1, temp);
128 visitRecurse(x + 1, y, temp);
129 visitRecurse(x, y + 1, temp);
130 } /* FUNCTION visit */
131
132 void process()
133 {
134 /* FUNCTION process */
135 int x, y;
136
137 for (x = 0; x < w; x ++)
138 {
139 for (y = 0; y < h; y ++)
140 {
141 if (VISITED != arr[x][y])
142 {
143 /* recursive visit*/
144 visit(x, y);
145 }/* recursive visit*/
146 }
147 }
148 DEBUG langDump();
149 } /* FUNCTION process */
150
151 void printRecurse(int i)
152 {
153 int cont = 0;
154 int x;
155 int maxmin = 9999999;
156
157 for (x = 0; ALPHASIZE > x; x ++)
158 {
159 if ( languages[x] > i)
160 {
161 cont = 1;
162 if (maxmin > languages[x])
163 {
164 maxmin = languages[x];
165 }
166 }
167 }
168
169 if (cont)
170 {
171 printRecurse(maxmin);
172 }
173
174 for (x = 0; ALPHASIZE > x; x ++)
175 {
176 if (languages[x] == i)
177 {
178 printf("%c: %d\n", 'a'+x, i);
179 }
180 }
181
182 }
183
184 void printOutput()
185 {
186 printRecurse(1);
187 }
188
189
190 void letterInit()
191 {
192 int x;
193 for ( x = 0; ALPHASIZE > x; x ++)
194 {
195 letters[x].num = languages[x];
196 letters[x].letter = 'a' + x;
197 /* printf("%c - %d\n", letters[x].letter, letters[x].num); */
198 }
199 }
200
201
202 int compare (const void * let1, const void * let2)
203 {
204 lang * l1 = (lang*)let1;
205 lang * l2 = (lang*)let2;
206
207 if (l1->num > l2->num)
208 {
209 return -1;
210 }
211 else if (l1->num < l2->num)
212 {
213 return +1;
214 }
215 else if (l1->letter > l2->letter)
216 {
217 return 1;
218 }
219 else
220 {
221 return -1;
222 }
223 }
224
225 void printSane()
226 {
227 int x;
228 DEBUG fprintf(stderr, "BEGIN printSane\n");
229 letterInit();
230 qsort(letters, ALPHASIZE, sizeof(lang), compare);
231 for (x=0; ((x < ALPHASIZE) && (0 != letters[x].num)); x++)
232 {
233 printf("%c: %d\n", letters[x].letter, letters[x].num);
234 }
235 }
236
237 int main ()
238 {
239 /* main */
240 int i;
241
242 init();
243 for (i=0; i<numberOfTimes; i++)
244 {
245 /* while */
246 printf("World #%d\n", i+1);
247 langInit();
248 getInput();
249 DEBUG dump();
250 process();
251 /* printOutput();*/
252 printSane();
253 } /* while */
254
255 return 1;
256 } /* main */
257
258