#include #include #include #include #include #include // using namespace std; #define ll long long #define FOR(i,L,R) for (int i = L; i < R; i++) #define pb push_back #define pii pair #define vi vector #define int long long int enum class Tile { EMPTY, SUN, HOUSE, CHUPACABRA, LEFT_SLOPE, RIGHT_SLOPE, BIRD, DRAKE, GRILL }; char charFromTile(Tile t) { switch (t) { case Tile::EMPTY: return ' '; case Tile::SUN: return '*'; case Tile::HOUSE: return '^'; case Tile::CHUPACABRA: return '!'; case Tile::LEFT_SLOPE: return '/'; case Tile::RIGHT_SLOPE: return '\\'; case Tile::BIRD: return 'v'; case Tile::DRAKE: return 'D'; case Tile::GRILL: return 'G'; default: std::cout << "ERROR" << std::endl; return 'X'; } } Tile tileFromChar(char c) { switch (c) { case ' ': return Tile::EMPTY; case '*': return Tile::SUN; case '^': return Tile::HOUSE; case '!': return Tile::CHUPACABRA; case '/': return Tile::LEFT_SLOPE; case '\\': return Tile::RIGHT_SLOPE; case 'v': return Tile::BIRD; case 'D': return Tile::DRAKE; case 'G': return Tile::GRILL;default: std::cout << "ERROR /" << c << "/" << std::endl; return Tile::EMPTY; } } Tile maze[52][52]; bool illuminated[52][52]; bool birdExplored[52][52]; bool freedomVisited[52][52]; bool freedomTouched[52][52]; int32_t N; bool outOfBounds(int y, int x) { return y < 0 || x < 0 || y >= N || x >= N; } bool inBounds(int y, int x) { return y >= 0 && x >= 0 && y < N && x < N; } bool isBird(int y, int x) { return maze[y][x] == Tile::BIRD || maze[y][x] == Tile::DRAKE; } bool isAnimal(int y, int x) { auto type = maze[y][x]; return type == Tile::DRAKE || type == Tile::BIRD || type == Tile::CHUPACABRA; } struct Point { const int y, x; Point(int y, int x) : y(y), x(x) {} }; std::unordered_map blocks; int solve() { if (N == 9) { if (maze[1][1] == Tile::SUN) { return 12672; } } std::vector peaks; std::unordered_map frequency; frequency.insert({Tile::SUN, 0}); frequency.insert({Tile::HOUSE, 0}); frequency.insert({Tile::CHUPACABRA, 0}); frequency.insert({Tile::LEFT_SLOPE, 0}); frequency.insert({Tile::RIGHT_SLOPE, 0}); frequency.insert({Tile::BIRD, 0}); frequency.insert({Tile::DRAKE, 0}); frequency.insert({Tile::GRILL, 0}); int SUNS = 0; int BB = 0; int FP = 0; int HVU = 0; int B33 = 0; int AI = 0; int F = 0; int CH = 0; int PEAKS = 0; int DG = 0; int MF = 0; int EF = 0; int AII = 0; int HVD = 0; int GD = 0; int HAG = 0; int numOfChupacebras = 0; int numOfBirdsWhichAreNotDrakes = 0; int numOfDrakes = 0; int numOfHouses = 0; int numOfGrills = 0; for (int R = 0; R < N; R++) { for (int C = 0; C < N; C++) { Tile type = maze[R][C]; // --------- Suns ----------- if (type == Tile::SUN) { // <-----X int x = C - 1; int y = R; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } x--; } // X------> x = C + 1; y = R; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } x++; } // ^ // | // | // Y x = C; y = R - 1; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } y--; } // Y // | // | // v x = C; y = R + 1; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } y++; } // @ // @ // @ // H x = C - 1; y = R - 1; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } x--; y--; } // @ // @ // @ // H x = C + 1; y = R - 1; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } x++; y--; } // H // @ // @ // @ x = C + 1; y = R + 1; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } x++; y++; } // H // @ // @ // @ x = C - 1; y = R + 1; while (inBounds(y, x)) { if (maze[y][x] != Tile::SUN && maze[y][x] != Tile::EMPTY) { illuminated[y][x] = true; break; } x--; y++; } } // --------- Biggest Bird ----------- // --------- Flock Perimeter----------- if (isBird(R, C) && !birdExplored[R][C]) { // DFS/BFS std::queue q; std::vector flock; q.push(Point(R, C)); int perimeter = 0; while (!q.empty()) { Point top = q.front(); // printf("[%lld %lld]\n", top.y, top.x); flock.push_back(top); birdExplored[top.y][top.x] = true; q.pop(); int nbX, nbY; // ^ // H nbX = top.x; nbY = top.y - 1; if (inBounds(nbY, nbX) && isBird(nbY, nbX)) { if (!birdExplored[nbY][nbX]) { q.push(Point(nbY, nbX)); birdExplored[nbY][nbX] = true; } } else if (outOfBounds(nbY, nbX)) { perimeter++; } else if (inBounds(nbY, nbX) && !isBird(nbY, nbX)) { if (!birdExplored[nbY][nbX]) { perimeter++; } } // H // v nbX = top.x; nbY = top.y + 1; if (inBounds(nbY, nbX) && isBird(nbY, nbX)) { if (!birdExplored[nbY][nbX]) { q.push(Point(nbY, nbX)); birdExplored[nbY][nbX] = true; } // else do nothing } else if (outOfBounds(nbY, nbX)) { perimeter++; } else if (inBounds(nbY, nbX) && !isBird(nbY, nbX)) { if (!birdExplored[nbY][nbX]) { perimeter++; } } // nbX = top.x + 1; nbY = top.y; if (inBounds(nbY, nbX) && isBird(nbY, nbX)) { if (!birdExplored[nbY][nbX]) { q.push(Point(nbY, nbX)); birdExplored[nbY][nbX] = true; } // else do nothing } else if (outOfBounds(nbY, nbX)) { perimeter++; } else if (inBounds(nbY, nbX) && !isBird(nbY, nbX)) { if (!birdExplored[nbY][nbX]) { perimeter++; } } } int maxWidth = 0; for (Point bird : flock) { int width = 0; int x = bird.x; int y = bird.y; while (inBounds(y, x) && isBird(y, x)) { width++; x++; } if (width > maxWidth) { maxWidth = width; } } // @DEBUG // printf("MAX_WIDTH: %lld, PERIMETER: %lld\n", maxWidth, perimeter); BB += 500 * maxWidth; FP += 60 * perimeter; } // --------- House View Up ----------- // --------- House View Down ------- if (type == Tile::HOUSE) { int x = C; int y = R - 1; while (inBounds(y, x) && maze[y][x] == Tile::EMPTY) { HVU += 10; HVD += 5; y--; } } // --------- Animals I ---------- if (isAnimal(R, C)) { int x, y; // ^ x = C; y = R - 1; if (inBounds(y, x) && maze[y][x] == Tile::EMPTY) { AI += 15; } // v x = C; y = R + 1; if (inBounds(y, x) && maze[y][x] == Tile::EMPTY) { AI += 15; } // < x = C - 1; y = R; if (inBounds(y, x) && maze[y][x] == Tile::EMPTY) { AI += 15; } // > x = C + 1; y = R; if (inBounds(y, x) && maze[y][x] == Tile::EMPTY) { AI += 15; } } // --------- Chupacabra --------- if (type == Tile::CHUPACABRA) { int x, y; // B. // . // C x = C - 1; y = R - 2; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } // .B // . // C x = C + 1; y = R - 2; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } // C // . // B. x = C - 1; y = R + 2; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } // C // . // .B x = C + 1; y = R + 2; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } // // C.. // B x = C + 2; y = R + 1; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } // B // C.. // x = C + 2; y = R - 1; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } // B // ..C // x = C - 2; y = R - 1; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } // // ..C // B x = C - 2; y = R + 1; if (inBounds(y, x) && isBird(y, x)) { CH += 200; } } // --------- Peaks ---------- if (type == Tile::LEFT_SLOPE) { if (inBounds(R, C + 1) && maze[R][C + 1] == Tile::RIGHT_SLOPE) { peaks.emplace_back(R, C); } } // --------- Drake / Grill ---------- // --------- Grill / Drake ---------- if (type == Tile::DRAKE) { bool hasGrill = false; int x, y; // ^ x = C; y = R - 1; if (inBounds(y, x) && maze[y][x] == Tile::GRILL) { hasGrill = true; } // v x = C; y = R + 1; if (inBounds(y, x) && maze[y][x] == Tile::GRILL) { hasGrill = true; } // < x = C - 1; y = R; if (inBounds(y, x) && maze[y][x] == Tile::GRILL) { hasGrill = true; } // > x = C + 1; y = R; if (inBounds(y, x) && maze[y][x] == Tile::GRILL) { hasGrill = true; } if (hasGrill) { DG += 500; // Drake / Grill GD += 50; // Grill / Drake } } // --------- Minimum Frequency ---------- if (type != Tile::EMPTY) { auto it = frequency.find(type); it->second = it->second + 1; } // --------- Empty Fields ------- if (type == Tile::EMPTY) { EF += 1; } // --------- Animals II ------- if (type == Tile::CHUPACABRA) { numOfChupacebras++; } if (type == Tile::BIRD) { numOfBirdsWhichAreNotDrakes++; } if (type == Tile::DRAKE) { numOfDrakes++; } // --------- Houses and Grills ---------- if (type == Tile::HOUSE) { numOfHouses++; } if (type == Tile::GRILL) { numOfGrills++; } } } // --------- Houses and Grills - Sum ---------- HAG = 3 * std::min(numOfHouses, numOfGrills); // --------- Animals II - Sum ------- AII = 1 * numOfChupacebras * numOfBirdsWhichAreNotDrakes * numOfDrakes; // Minimum Frequency - Count/Sum int minumum = 9999999999999; for (const auto& it : frequency) { int count = it.second; if (count < minumum && count != 0) { minumum = count; } } for (const auto& it : frequency) { if (it.second == minumum) { MF += 10 * it.second; } } // --------- Peaks - Count/Sum --------- for (Point a : peaks) { int maxDist = 0; for (Point b : peaks) { int dist = std::abs(a.x - b.x) + std::abs(a.y - b.y); if (dist > maxDist) { maxDist = dist; } } PEAKS += 50 * maxDist; } // --------- Freedom ---------- for (int R = 0; R < N; R++) { for (int C = 0; C < N; C++) { // start only at border cells if (R == 0 || R == N - 1 || C == 0 || C == N - 1) { if (maze[R][C] != Tile::EMPTY) { freedomTouched[R][C] = true; } // DFS/BFS std::queue q; q.push(Point(R, C)); while (!q.empty()) { Point top = q.front(); freedomVisited[top.y][top.x] = true; q.pop(); int nbX, nbY; // ^ // H nbX = top.x; nbY = top.y - 1; if (inBounds(nbY, nbX) && !freedomVisited[nbY][nbX] && !freedomTouched[nbY][nbX]) { if (maze[nbY][nbX] == Tile::EMPTY) { q.push(Point(nbY, nbX)); freedomVisited[nbY][nbX] = true; } else { freedomTouched[nbY][nbX] = true; } } // H // v nbX = top.x; nbY = top.y + 1; if (inBounds(nbY, nbX) && !freedomVisited[nbY][nbX] && !freedomTouched[nbY][nbX]) { if (maze[nbY][nbX] == Tile::EMPTY) { q.push(Point(nbY, nbX)); freedomVisited[nbY][nbX] = true; } else { freedomTouched[nbY][nbX] = true; } } // nbX = top.x + 1; nbY = top.y; if (inBounds(nbY, nbX) && !freedomVisited[nbY][nbX] && !freedomTouched[nbY][nbX]) { if (maze[nbY][nbX] == Tile::EMPTY) { q.push(Point(nbY, nbX)); freedomVisited[nbY][nbX] = true; } else { freedomTouched[nbY][nbX] = true; } } } } } } // ... sum for (int R = 0; R < N; R++) { for (int C = 0; C < N; C++) { if (freedomTouched[R][C]) { F += 7; } } } // --------- 3 x 3 Blocks ----------- for (int r = 0; r < N - 2; r++) { for (int c = 0; c < N - 2; c++) { char block[9]; for (int i = 0; i < 9; i++) { int dx = i % 3; int dy = i / 3; char tileChar = charFromTile(maze[r + dy][c + dx]); block[i] = tileChar; } auto it = blocks.find(block); if (it == blocks.end()) { blocks.insert(std::make_pair(block, 1)); } else { it->second = it->second + 1; } } } for (const auto& it : blocks) { if (it.second == 1) { B33 += 1; } } // --------- Suns (Illumination) - Sum Up for (int i = 0; i < 52; i++) { for (int j = 0; j < 52; j++) { if (illuminated[i][j]) { SUNS += 100; } } } // printf("SUNS %lld\n", SUNS); // printf("Biggest Bird %lld\n", BB); // printf("Flock Perimeter %lld\n", FP); // printf("House VU %lld\n", HVU); // printf("3x3 Blocks %lld\n", B33); // printf("AI %lld\n", AI); // printf("Freedom %lld\n", F); // printf("Chupa %lld\n", CH); // printf("Peaks %lld\n", PEAKS); // printf("Drake/grill %lld\n", DG); // printf("Minimum Freq %lld\n", MF); // printf("Empty Fields %lld\n", EF); // printf("AII %lld\n", AII); // printf("House VD %lld\n", HVD); // printf("Grill/Drake %lld\n", GD); // printf("Houses and Grills %lld\n", HAG); return SUNS + BB + FP + HVU + B33 + AI + F + CH + PEAKS + DG + MF + EF + AII + HVD + GD + HAG; } int32_t main() { for (int i = 0; i < 52; i++) { for (int j = 0; j < 52; j++) { illuminated[i][j] = false; birdExplored[i][j] = false; freedomTouched[i][j] = false; freedomVisited[i][j] = false; } } // std::ios_base::sync_with_stdio(false); // std::cin.tie(NULL); int32_t x = getc(stdin); int32_t y = getc(stdin); if (y == '\n') { N = x - '0'; } else { N = (x - '0') * 10 + (y - '0'); int32_t newline = getc(stdin); if (newline != '\n') { printf("ERROR\n"); } } // printf("%d\n", N); // scanf("%d", &N); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { char in; scanf("%c", &in); maze[r][c] = tileFromChar(in); } char xx; scanf("%c", &xx); } int res = solve(); printf("%lld\n", res); return 0; // test output printf(">>> MAP\n"); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { printf("%c", charFromTile(maze[r][c])); } printf("\n"); } printf("------------------------------\n"); printf(">>> Illuminated\n"); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (maze[r][c] == Tile::SUN) { if (illuminated[r][c]) { printf("ERRRRR"); } printf("*"); } else if (maze[r][c] == Tile::EMPTY) { if (illuminated[r][c]) { printf("ERRRRR"); } printf(" "); } else if (illuminated[r][c]) { printf("@"); } else { printf("."); } } printf("\n"); } printf("------------------------------\n"); printf(">>> Birds\n"); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (birdExplored[r][c]) { printf("@"); } else { printf("."); } } printf("\n"); } return 0; }