1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Check if a tree is newly seen, by being taller than max or not
//
// If it is seen, update max.
//
// If the tree is seen, and has not been seen before, return 1
// Otherwise return 0
int
tree_seen(int * max, unsigned char * tree)
{
int height = (*tree & 0x7F) - '0';
int seen = 0;
if (height > *max) {
if (!(*tree & 0x80u)) {
*tree |= 0x80u;
++seen;
}
*max = height;
}
return seen;
}
// Check the number of seen trees in a forest
int
forest_seen(unsigned char * forest, int rows, int cols)
{
int i, j, max, seen = 0;
// For each row...
for (i = 0; i < rows; ++i) {
// Check which trees can be newly seen from the left
for (j = 0, max = -1; j < cols - 1 && max < 9; ++j) {
seen += tree_seen(&max, forest + i * cols + j);
}
// Check which trees can be newly seen from the right
for (j = cols - 2, max = -1; j >= 0 && max < 9; --j) {
seen += tree_seen(&max, forest + i * cols + j);
}
}
// For each column...
for (j = 0; j < cols - 1; ++j) {
// Check which trees can be newly seen from the top
for (i = 0, max = -1; i < rows && max < 9; ++i) {
seen += tree_seen(&max, forest + i * cols + j);
}
// Check which trees can be newly seen from the bottom
for (i = rows - 1, max = -1; i >= 0 && max < 9; --i) {
seen += tree_seen(&max, forest + i * cols + j);
}
}
return seen;
}
int
main()
{
int cols = 0, rows = 0;
char * forest;
// Read first line
forest = malloc(BUFSIZ);
if (!fgets(forest, BUFSIZ, stdin)) {
fprintf(stderr, "Need more input!\n");
return -1;
}
cols = strlen(forest);
if (cols < 2 || forest[cols - 1] != '\n') {
fprintf(stderr, "Unexpected first line! (length %d)\n", cols);
return -1;
}
++rows;
while (1) {
// Resize forest for next line.
// Do the dumb thing and rely on realloc() to overallocate and manage
// exponential growth of the underlying buffer
//
// If we were expecting huge input, we could just ask for a filename and
// mmap() it.
char * p = realloc(forest, (long) cols * (rows + 1) + 1);
if (!p) {
fprintf(stderr, "Realloc %ld fail! (%s)\n",
(long) cols * (rows + 1) + 2, strerror(errno));
free(forest);
return -1;
}
forest = p;
// Read line.
p = forest + cols * rows;
if (!fgets(p, cols + 1, stdin))
break;
// Check line length
if (strlen(p) != cols || p[cols - 1] != '\n') {
fprintf(stderr, "Unexpected line length for %s\n", p);
free(forest);
return -1;
}
++rows;
}
printf("Trees seen: %d\n", forest_seen((unsigned char *) forest, rows, cols));
free(forest);
return 0;
}
|
