#include #include #include #define BUFFER_SIZE 128 #define cti(c) (c - '0') // For simplicity we know the dimensions #define MAP_WIDTH 99 #define MAP_HEIGHT 99 enum DIRECTION { TOP, RIGHT, BOTTOM, LEFT }; int map[MAP_WIDTH][MAP_HEIGHT]; int visible[MAP_WIDTH][MAP_HEIGHT]; int is_visible_from(int, int, enum DIRECTION, int); int is_visible(int, int); int scenic_score(int, int); int scenic[4] = {0,0,0,0}; int main() { char c; int col = 0, row = 0; while ((c = getchar()) != EOF) { if (c == '\n') { col = 0; row++; continue; } map[col][row] = cti(c); col++; } // Nothing is visible first for (int i = 0; i < MAP_WIDTH; i++) for (int j = 0; j < MAP_HEIGHT; j++) visible[i][j] = 0; int sum = 0; // Let's iterate all trees and find if they are visible // It would be cleaner to just run a scan from the edges // and mark trees that are visible (higher than the current max) // // But where's the recursion in that? for (int i = 0; i < MAP_HEIGHT; i++) for (int j = 0; j < MAP_WIDTH; j++) { visible[j][i] = is_visible(j, i); sum += visible[j][i]; } printf("%i\n", sum); int bestScenic = 0, tmp; for (int i = 0; i < MAP_HEIGHT; i++) for (int j = 0; j < MAP_WIDTH; j++) { tmp = scenic_score(j, i); if (bestScenic < tmp) { bestScenic = tmp; } } printf("%i\n", bestScenic); } int is_visible_from(int col, int row, enum DIRECTION direction, int size) { // Ugly solution but it is easier to do this to solve task 2 if (row != 0 && col != 0 && row != MAP_HEIGHT - 1 && col != MAP_WIDTH - 1) scenic[direction]++; switch (direction) { case TOP: if (row == 0 || (map[col][row-1] < size && is_visible_from(col, row - 1, TOP, size))) { return 1; } break; case RIGHT: if (col == MAP_WIDTH - 1 || (map[col+1][row] < size && is_visible_from(col + 1, row, RIGHT, size))) { return 1; } break; case BOTTOM: if (row == MAP_HEIGHT - 1 || (map[col][row+1] < size && is_visible_from(col, row + 1, BOTTOM, size))) { return 1; } break; case LEFT: if (col == 0 || (map[col-1][row] < size && is_visible_from(col - 1, row, LEFT, size))) { return 1; } break; } return 0; } int is_visible(int col, int row) { // If they are on the visibility map if (visible[col][row]) return 1; if (is_visible_from(col, row, TOP, map[col][row]) || is_visible_from(col, row, RIGHT, map[col][row]) || is_visible_from(col, row, BOTTOM, map[col][row]) || is_visible_from(col, row, LEFT, map[col][row])) return 1; return 0; } int scenic_score(int col, int row) { for (int i = 0; i < 4; i++) { scenic[i] = 0; } is_visible_from(col, row, TOP, map[col][row]); is_visible_from(col, row, RIGHT, map[col][row]); is_visible_from(col, row, BOTTOM, map[col][row]); is_visible_from(col, row, LEFT, map[col][row]); int result = 1; for (int i = 0; i < 4; i++) { result *= scenic[i]; } return result; }