#include #include #include #include #include #include #include #include using namespace std; constexpr char EMPTY = ' '; constexpr char SUN = '*'; constexpr char HOUSE = '^'; constexpr char CHUPACABRA = '!'; constexpr char LEFT_SLOPE = '/'; constexpr char RIGHT_SLOPE = '\\'; constexpr char BIRD = 'v'; constexpr char DRAKE = 'D'; constexpr char GRILL = 'G'; bool isBird(char cell) { return (cell == BIRD || cell == DRAKE); } std::set CELLS = {EMPTY, SUN, HOUSE, CHUPACABRA, LEFT_SLOPE, RIGHT_SLOPE, BIRD, DRAKE, GRILL}; using VEC2D = vector>; VEC2D input() { int N; cin >> N; cin.ignore(); vector> rez(N, vector(N)); for (int y = 0; y < N; ++y){ string s; getline(cin, s); for (int x = 0; x < N; ++x) { rez[x][y] = s[x]; if (CELLS.find(rez[x][y]) == CELLS.end()) throw std::runtime_error("INVALID CELL: " + std::to_string(rez[x][y])); } } return rez; } bool in_bounds(const VEC2D& field, int x, int y) { return x >= 0 && x < (int)field.size() && y >= 0 && y < (int)field.size(); } //CHECK FOR SUNS void suns_check_impl(int x, int y, const VEC2D& field, VEC2D& sunMap) { std::tuple moves[8] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1} }; for (int i = 0; i < 8; ++i) { const auto& [mx, my] = moves[i]; int px = x + mx; int py = y + my; while (in_bounds(field, px, py)) { if (field[px][py] == SUN) break; if (field[px][py] != EMPTY) { sunMap[px][py] = 1; break; } px += mx; py += my; } } } int suns(const VEC2D& field) { VEC2D sunMap(field.size(), vector(field.size(), 0)); for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == SUN) suns_check_impl(x, y, field, sunMap); } } int rez = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (sunMap[x][y] == 1) rez += 100; } } return rez; } void floodFill(int x, int y, const VEC2D& field, VEC2D& flock) { if (!in_bounds(field, x, y) || flock[x][y] == 1 || !isBird(field[x][y])) return; flock[x][y] = 1; floodFill(x + 1, y, field, flock); floodFill(x - 1, y, field, flock); floodFill(x, y + 1, field, flock); floodFill(x, y - 1, field, flock); } int flockWidth(const VEC2D& flock) { int maxSz = 0; for (int y = 0; y < (int)flock.size(); ++y) { int sz = 0; for (int x = 0; x < (int)flock.size(); ++x) { if (flock[x][y] == 1) sz++; else { maxSz = max(maxSz, sz); sz = 0; } } maxSz = max(maxSz, sz); } return maxSz; } int flockPerimeter(const VEC2D& flock) { int rez = 0; for (int y = 0; y < (int)flock.size(); ++y) { for (int x = 0; x < (int)flock.size(); ++x) { if (flock[x][y] == 1) { if (!in_bounds(flock, x - 1, y) || flock[x - 1][y] == 0) rez++; if (!in_bounds(flock, x + 1, y) || flock[x + 1][y] == 0) rez++; if (!in_bounds(flock, x, y - 1) || flock[x][y - 1] == 0) rez++; if (!in_bounds(flock, x, y + 1) || flock[x][y + 1] == 0) rez++; } } } return rez; } void mergeBirdMap(VEC2D& birdMap, const VEC2D& flock) { for (int y = 0; y < (int)birdMap.size(); ++y) { for (int x = 0; x < (int)birdMap.size(); ++x) { if (flock[x][y] == 1) birdMap[x][y] = 1; } } } int birds(const VEC2D& field) { int rez = 0; VEC2D birdMap(field.size(), vector(field.size(), 0)); for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (isBird(field[x][y]) && birdMap[x][y] == 0) { VEC2D flock(field.size(), vector(field.size(), 0)); floodFill(x, y, field, flock); rez += 500 * flockWidth(flock); rez += 60 * flockPerimeter(flock); mergeBirdMap(birdMap, flock); } } } return rez; } void housesImpl(int x, int y, const VEC2D& field, VEC2D& houseMap) { std::tuple moves[1] = { {0, -1} }; for (int i = 0; i < 1; ++i) { const auto& [mx, my] = moves[i]; int px = x + mx; int py = y + my; while (in_bounds(field, px, py)) { if (field[px][py] != EMPTY) { break; } houseMap[px][py] = 1; px += mx; py += my; } } } int houses(const VEC2D& field) { int rez = 0; VEC2D houseMap(field.size(), vector(field.size(), 0)); for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == HOUSE) { housesImpl(x, y, field, houseMap); } } } for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (houseMap[x][y] == 1) rez += 10; } } return rez; } int blocks(const VEC2D& field) { unordered_set S; int rez = 0; std::string s(9, 0); for (int y = 0; y < static_cast(field.size()) - 2; ++y) { for (int x = 0; x < static_cast(field.size()) - 2; ++x) { int c = 0; for (int px = 0; px < 2; ++px) { for (int py = 0; py < 2; ++py) { s[c++] = field[x + px][y + py]; } } if (S.insert(s).second == true) { rez ++; } } } return rez; } int animals1(const VEC2D& field) { int rez = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == BIRD || field[x][y] == DRAKE || field[x][y] == CHUPACABRA) { if (in_bounds(field, x - 1, y) && field[x - 1][y] == EMPTY) rez+=15; if (in_bounds(field, x + 1, y) && field[x + 1][y] == EMPTY) rez+=15; if (in_bounds(field, x, y - 1) && field[x][y - 1] == EMPTY) rez+=15; if (in_bounds(field, x, y + 1) && field[x][y + 1] == EMPTY) rez+=15; } } } return rez; } void floodFill2(int x, int y, const VEC2D& field, VEC2D& freedom) { if (!in_bounds(field, x, y)) return; if (freedom[x][y] == 1) return; freedom[x][y] = 1; if (field[x][y] != EMPTY) return; floodFill2(x + 1, y, field, freedom); floodFill2(x - 1, y, field, freedom); floodFill2(x, y + 1, field, freedom); floodFill2(x, y - 1, field, freedom); } int freedom(const VEC2D& field) { VEC2D freedomMap(field.size(), vector(field.size(), 0)); for (int i = 0; i < (int)field.size(); ++i) { floodFill2(i, 0, field, freedomMap); floodFill2(0, i, field, freedomMap); floodFill2(i, static_cast(field.size()) - 1, field, freedomMap); floodFill2(static_cast(field.size()) - 1, i, field, freedomMap); } int rez = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (freedomMap[x][y] == 1 && field[x][y] != EMPTY) { rez += 7; } } } return rez; } void chupacabraImpl(int x, int y, const VEC2D& field, VEC2D& chupaMap) { std::tuple moves[8]{ { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } }; for (const auto& [mx, my] : moves) { int nx = x + mx; int ny = y + my; if (in_bounds(field, nx, ny) && isBird(field[nx][ny])) { chupaMap[nx][ny] = 1; } } } int chupacabra(const VEC2D& field) { VEC2D chupaMap(field.size(), vector(field.size(), 0)); for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == CHUPACABRA) { chupacabraImpl(x, y, field, chupaMap); } } } int rez = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (chupaMap[x][y] == 1) rez += 200; } } return rez; } int peaks(const VEC2D& field) { std::vector> peakArr; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < static_cast(field.size()) - 1; ++x) { if (field[x][y] == LEFT_SLOPE && field[x + 1][y] == RIGHT_SLOPE) { peakArr.emplace_back(x, y); } } } int rez = 0; for (const auto& [x1, y1]: peakArr) { int maxDist = 0; for (const auto& [x2, y2] : peakArr) { int dist = abs(x1 - x2) + abs(y1 - y2); maxDist = max(dist, maxDist); } rez += 50 * maxDist; } return rez; } bool isNeighbour(const VEC2D& field, int x, int y, char target) { if (in_bounds(field, x - 1, y) && field[x - 1][y] == target) return true; if (in_bounds(field, x + 1, y) && field[x + 1][y] == target) return true; if (in_bounds(field, x, y - 1) && field[x][y - 1] == target) return true; if (in_bounds(field, x, y + 1) && field[x][y + 1] == target) return true; return false; } int drakeGrill(const VEC2D& field) { int rez = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == DRAKE) { if (isNeighbour(field, x, y, GRILL)) rez += 500; } } } return rez; } int MinFreq(const VEC2D& field) { std::map mp; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] != EMPTY) { auto it = mp.find(field[x][y]); if (it == mp.end()) { mp[field[x][y]] = 1; } else { mp[field[x][y]] += 1; } } } } if (mp.size() == 0) return 0; int minval = numeric_limits::max(); for (const auto& [k, v] : mp) { minval = min(v, minval); } int rez = 0; for (const auto& [k, v] : mp) { if (v == minval) { rez += 10 * minval; } } return rez; } int emptys(const VEC2D& field) { int rez = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == EMPTY) { rez++; } } } return rez; } int animalsAll(const VEC2D& field) { int chupa = 0; int bird = 0; int drake = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == CHUPACABRA) chupa++; else if (field[x][y] == BIRD) bird++; else if (field[x][y] == DRAKE) drake++; } } return chupa * bird * drake; } int housesDown(const VEC2D& field) { int rez = 0; VEC2D houseMap(field.size(), vector(field.size(), 0)); for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == HOUSE) { housesImpl(x, y, field, houseMap); } } } for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (houseMap[x][y] == 1) rez += 5; } } return rez; } int grillDrake(const VEC2D& field) { int rez = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == GRILL) { if (isNeighbour(field, x, y, DRAKE)) rez += 50; } } } return rez; } int houseGrill(const VEC2D& field) { int houses = 0; int grills = 0; for (int y = 0; y < (int)field.size(); ++y) { for (int x = 0; x < (int)field.size(); ++x) { if (field[x][y] == HOUSE) houses++; if (field[x][y] == GRILL) grills++; } } return 3 * min(houses, grills); } int main() { auto field = input(); int rez = 0; rez += suns(field); rez += birds(field); //1480 rez += houses(field); // 0 rez += blocks(field); // rez += animals1(field); rez += freedom(field); rez += chupacabra(field); rez += peaks(field); rez += drakeGrill(field); rez += MinFreq(field); rez += emptys(field); rez += animalsAll(field); rez += housesDown(field); rez += grillDrake(field); rez += houseGrill(field); cout << rez; return 0; }