/home/toolbox/public_html/solutions/8/871/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 <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /* fprintf(stderr, "functionName: message", varslist); */
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2018-03-16
20 * Purpose: fun
21 * Problem: 871 - Counting Cells in a Blob
22 */
23
24 /*
25 * This template reads data a specified number of times.
26 */
27
28 #define MAX_DIM 27
29 #define EMPTY -1
30 #define FILLED 0
31 #define BORDER -9
32
33 int numberOfTimes;
34 int grid[MAX_DIM][MAX_DIM];
35 int siz;
36 char line[MAX_DIM];
37 int width;
38 int Roff[8] = { 0, 1, 1, 1, 0, -1, -1, -1};
39 int Coff[8] = { 1, 1, 0, -1, -1, -1, 0, 1};
40
41 void init()
42 {
43 /* FUNCTION init */
44 scanf("%d ", &numberOfTimes);
45 } /* FUNCTION init */
46
47 void dump()
48 {
49 /* FUNCTION dump */
50 int i;
51 int j;
52
53 printf("Grid is %d x %d\n", siz, width);
54 for (i=0; siz>=i; i++)
55 {
56 /* each row */
57 printf(" ");
58 for (j=0; width>=j; j++)
59 {
60 /* for each column */
61 printf("%3d", grid[i][j]);
62 } /* for each column */
63 printf("\n");
64 } /* each row */
65 } /* FUNCTION dump */
66
67 int valu(char x)
68 {
69 /* FUNCTION valu */
70 return ('0' == x) ? EMPTY : FILLED;
71 } /* FUNCTION valu */
72
73 void getInput()
74 {
75 /* FUNCTION getInput */
76 int i;
77 int j;
78 int lineRead;
79
80 siz = 1;
81 lineRead = (NULL != fgets(line, MAX_DIM, stdin));
82 width = strlen(line);
83 DEBUG printf("siz = %d lineRead = %d width = %d line = [%s]\n", siz, lineRead, width, line);
84 while (lineRead)
85 {
86 /* while */
87 for (i=1; width>i; i++)
88 {
89 /* for each column */
90 grid[siz][i] = valu(line[i-1]);
91 } /* for each column */
92 siz++;
93 lineRead = (NULL != fgets(line, MAX_DIM, stdin));
94 lineRead = lineRead && (1 < strlen(line));
95 DEBUG printf("i = %d siz = %d lineRead = %d width = %d line = [%s]\n", i, siz, lineRead, width, line);
96 } /* while */
97 /* fill in a border because I like borders */
98 grid[0][0] = BORDER;
99 grid[siz][0] = BORDER;
100 grid[0][width] = BORDER;
101 grid[siz][width] = BORDER;
102 for (i=1; siz>i; i++)
103 {
104 grid[i][0] = BORDER;
105 grid[i][width] = BORDER;
106 }
107 for (j=1; width>j; j++)
108 {
109 grid[0][j] = BORDER;
110 grid[siz][j] = BORDER;
111 }
112 } /* FUNCTION getInput */
113
114 int countThem(int mark, int r, int c)
115 {
116 /* FUNCTON countThem */
117 int i;
118 int tot = 0;
119
120 for(i=0; 8>i; i++)
121 {
122 /* for each possible neighbor */
123 if (FILLED == grid[r + Roff[i]][c + Coff[i]])
124 {
125 /* found another part of this blob */
126 grid[r + Roff[i]][c + Coff[i]] = mark;
127 tot++;
128 tot = tot + countThem(mark, r + Roff[i], c + Coff[i]);
129 } /* found another part of this blob */
130 } /* for each possible neighbor */
131 return tot;
132 } /* FUNCTON countThem */
133
134 void process()
135 {
136 /* FUNCTION process */
137 int i;
138 int j;
139 int cnt = 1;
140 int mx = 0;
141 int tmp;
142
143 DEBUG dump();
144 for (i=1; siz>i; i++)
145 {
146 /* for each row */
147 for (j=1; width>j; j++)
148 {
149 /* for each column */
150 if (FILLED == grid[i][j])
151 {
152 /* found a new blob */
153 DEBUG printf("grid[%d][%d] = %d ", i, j, cnt);
154 grid[i][j] = cnt;
155 tmp = 1 + countThem(cnt, i, j);
156 mx = (tmp > mx) ?tmp : mx;
157 DEBUG printf(" tot = %d mx = %d\n", tmp, mx);
158 cnt++;
159 } /* found a new blob */
160 } /* for each column */
161 } /* for each row */
162 DEBUG dump();
163 printf("%d\n", mx);
164 } /* FUNCTION process */
165
166 int main()
167 {
168 /* main */
169 int i;
170
171 init();
172 for (i=0; i<numberOfTimes; i++)
173 {
174 /* while */
175 if (0 != i)
176 {
177 printf("\n");
178 }
179 getInput();
180 process();
181 } /* while */
182
183 return EXIT_SUCCESS;
184 } /* main */
185
186