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