/home/toolbox/public_html/solutions/110/11094/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (TRUE)
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 20250409
19 * Purpose: fun
20 * Problem: 11094 - Continents
21 */
22
23 /*
24 * This template reads data until a terminating value is reached.
25 */
26
27 /* stuff you need to know to solve this problem:
28 *
29 * map max size is 20 x 20
30 * map wraps horizontaolly (i.e. the first pixel is considered adjacent to the last pixel on the row
31 * map does not wrap vertically -- map is a cylinder
32 * Letters for land and water are not know. YOu have to look at the kings starting spot (x,y) to
33 * determine the letter that is land, the other letter is water
34 * test cases end by hitting end of file while trying to read in the next map size
35 * Diagonals don't count only edge connected, this means that the most number of continents could be
36 * 100
37 *
38 * My implementation tweaks
39 * M,N are 0 to N-1 in problem -- I have translated to 1 to N so that I can have a guard buffer.
40 * That also means that I have to adjust the king's location (x,y)
41 * I am going to change all the land to L and all the water to W (just because)
42 */
43
44 #define MAX_BUFF 22
45 #define LAND 'L'
46 #define WATER 'W'
47 #define GUARD '.'
48 #define FILL 'o';
49
50 int m;
51 int n;
52 char map[MAX_BUFF][MAX_BUFF];
53 int kx;
54 int ky;
55
56 void init()
57 {
58 /* FUNCTION init */
59 int i;
60 int j;
61
62 for (i=0; i<MAX_BUFF; i++)
63 for (j=0; j<MAX_BUFF; j++)
64 map[i][j] = GUARD;
65 } /* FUNCTION init */
66
67 void dump()
68 {
69 /* FUNCTION dump */
70 int i;
71 int j;
72
73 printf("start: (%d, %d)\n", kx, ky);
74 for (i=0; i<MAX_BUFF; i++)
75 {
76 /* for each row */
77 printf("%2d:", i);
78 for (j=0; j<MAX_BUFF; j++)
79 printf("%c", map[i][j]);
80 printf("\n");
81 } /* for each row */
82
83 } /* FUNCTION dump */
84
85 void fixLetters()
86 {
87 /* FUNCTION fixLetters */
88 int i;
89 int j;
90 char land;
91 char water;
92
93 land = map[kx][ky];
94 for (i=1; i<=m; i++)
95 {
96 /* for each row */
97 for (j=1; j<=n; j++)
98 {
99 /* for each column */
100 if (land == map[i][j])
101 {
102 /* set it to land */
103 map[i][j] = LAND;
104 } /* set it to land */
105 else
106 {
107 /* set it to WATER */
108 map[i][j] = WATER;
109 } /* set it to WATER */
110 } /* for each column */
111 } /* for each row */
112 } /* FUNCTION fixLetters */
113
114 int getInput()
115 {
116 /* FUNCTION getInput */
117 int dataReadFlag;
118 int i;
119 int j;
120 char nl;
121
122 dataReadFlag = 2 == scanf(" %d %d ", &m, &n);
123 if (dataReadFlag)
124 {
125 /* get rest of data record */
126 for (i=1; i<=m; i++)
127 {
128 /* for each row */
129 for (j=1; j<=n; j++)
130 scanf("%c", &map[i][j]);
131 scanf("%c", &nl); /* skip newline */
132 } /* for each row */
133 scanf(" %d %d ", &kx, &ky);
134 kx++;
135 ky++; /* adjust King's location to 1-based indexing */
136 fixLetters();
137 } /* get rest of data record */
138 return (dataReadFlag);
139 } /* FUNCTION getInput */
140
141 int fill(int x, int y, char fc)
142 {
143 /* FUNCTION fill */
144 int toreturn = 0;
145 int xa;
146 int ya;
147
148 xa = x;
149 ya = y;
150 if (y > n)
151 {
152 y = 1; /* handle wrap arround */
153 }
154 if (1 > y)
155 {
156 y = n; /* handle wrap arround */
157 }
158 DEBUG printf("checking (%d, %d) (%d, %d) [%c]\n", xa, ya, x, y, map[x][y]);
159 /* since I have a guard ariund the map, I do not have to worry about x being 0 or N+1 */
160 if (LAND == map[x][y])
161 {
162 /* found land */
163 toreturn = 1;
164 map[x][y] = FILL;
165 map[x][y] = fc;
166 toreturn = toreturn + fill(x + 1, y, fc);
167 toreturn = toreturn + fill(x - 1, y, fc);
168 toreturn = toreturn + fill(x, y + 1, fc);
169 toreturn = toreturn + fill(x, y - 1, fc);
170 } /* found land */
171 return toreturn;
172 } /* FUNCTION fill */
173
174 void process()
175 {
176 /* FUNCTION process */
177 int tmp;
178 int max = 0;
179 int i;
180 int j;
181 char fc = 'a';
182
183 DEBUG dump();
184 tmp = fill(kx, ky, 'K');
185 DEBUG printf("king's continent blocks: %d\n", tmp);
186 DEBUG dump();
187 for (i=1; i<=m; i++)
188 {
189 /* for each row */
190 for (j=1; j<=n; j++)
191 {
192 /* for each column */
193 if (LAND == map[i][j])
194 {
195 /* found a new continent */
196 tmp = fill(i, j, fc);
197 fc++;
198 DEBUG printf("tmp %d\n", tmp);
199 if (tmp > max)
200 {
201 max = tmp;
202 }
203 } /* found a new continent */
204 } /* for each column */
205 } /* for each row */
206 DEBUG dump();
207 printf("%d\n", max);
208 } /* FUNCTION process */
209
210 int main()
211 {
212 /* main */
213 int moreToDo;
214
215 init();
216 moreToDo = getInput();
217 while (moreToDo)
218 {
219 /* while */
220 process();
221 moreToDo = getInput();
222 } /* while */
223
224 return EXIT_SUCCESS;
225 } /* main */
226