/home/toolbox/public_html/solutions/110/11094/b.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)
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) { y = 1; } /* handle wrap arround */
151 /* if (1 > y) { y = n; } /* handle wrap arround */
152 printf("checking (%d, %d) (%d, %d) [%c]\n", xa, ya, x, y, map[x][y]);
153 /* since I have a guard ariund the map, I do not have to worry about x being 0 or N+1 */
154 if (LAND == map[x][y])
155 {
156 /* found land */
157 toreturn = 1;
158 map[x][y] = FILL;
159 toreturn = toreturn + fill(x + 1, y);
160 toreturn = toreturn + fill(x - 1, y);
161 toreturn = toreturn + fill(x, y + 1);
162 toreturn = toreturn + fill(x, y - 1);
163 } /* found land */
164 return toreturn;
165 } /* FUNCTION fill */
166
167 void process()
168 {
169 /* FUNCTION process */
170 int tmp;
171 int max = 0;
172 int i;
173 int j;
174
175 DEBUG dump();
176 tmp = fill(kx, ky);
177 DEBUG printf("king's continent blocks: %d\n", tmp);
178 DEBUG dump();
179 for (i=1; i<=m; i++)
180 {
181 /* for each row */
182 for (j=1; j<=n; j++)
183 {
184 /* for each column */
185 if (LAND == map[i][j])
186 {
187 /* found a new continent */
188 tmp = fill(i, j);
189 printf("tmp %d\n", tmp);
190 if (tmp > max)
191 {
192 max = tmp;
193 }
194 } /* found a new continent */
195 } /* for each column */
196 } /* for each row */
197 DEBUG dump();
198 printf("%d\n", max);
199 } /* FUNCTION process */
200
201 int main()
202 {
203 /* main */
204 int moreToDo;
205
206 init();
207 moreToDo = getInput();
208 while (moreToDo)
209 {
210 /* while */
211 process();
212 moreToDo = getInput();
213 } /* while */
214
215 return EXIT_SUCCESS;
216 } /* main */
217