#ifndef LOCAL #pragma GCC optimize("O3") #endif #include using namespace std; #define sim template muu & operator<<( #define ris return *this #define R22(r) sim> typename enable_if<1 r sizeof(dud(0)),muu&>::type operator<<(c g) { sim> struct rge {c b, e;}; sim> rge range(c i, c j) {return {i, j};} sim> auto dud(c*r)->decltype(cerr << *r); sim> char dud(...); struct muu { #ifdef LOCAL stringstream a; ~muu() {cerr << a.str() << endl;} R22(<) a << boolalpha << g; ris;} R22(==) ris << range(begin(g), end(g));} sim, class b mor pair r) {ris << "(" << r.first << ", " << r.second << ")";} sim mor rge u) { a << "["; for (c i = u.b; i != u.e; ++i) *this << ", " + 2 * (i == u.b) << *i; ris << "]"; } #define qel(t) sim, class d, class...e mor t r) {ris << *(d*)&r;} qel(stack) qel(queue) qel(priority_queue) template r) { a << "("; int q = 0; apply([&](c...x){((*this << ", " + 2 * !q++ << x), ...);}, r); ris << ")"; } #else sim mor const c&){ris;} #endif }; #define imie(r...) "[" #r ": " << (r) << "] " #define arr(a, i) "[" #a imie(i) ": " << a[i] << "] " #define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] " #define range(a, b) "[[" #a ", " #b "): " << range(a, b) << "] " #define debug muu() << __FUNCTION__ << "#" << __LINE__ << ": " using ll = long long; using ld = long double; using unt = unsigned int; using pii = pair; using vpii = vector ; using ull = unsigned long long; using vi = vector; using Pii = pii; using vll = vector ; sim> void mini(c &a, const c& b) {if (a > b) a = b;} sim> void maxi(c &a, const c& b) {if (a < b) a = b;} const int nax = 55; char board[nax][nax]; int n; char get_cell(int i, int j) { if (i >= 0 && j >= 0 && i < n && j < n) return board[i][j]; return '#'; } char get_cell(pii x) { return get_cell(x.first, x.second); } bool illuminated[nax][nax]; //Operatory na parach: (a, b) + c = (a + c, b + c), (a, b) + (c, d) = (a + c, b + d), a + (b, c) = (a + b, a + c) //(a, b) += (c, d) -> (a + c, b + d) (a, b) += c -> (a + c, b + c) //Automatycznie przenosi się na operatory na większych krotkach, np (a, (b, c)) * (e, (f, g)) = (a * e, (b, c) * (f, g)) = (a * e, (b * f, c * g)) //((a, b), c) % (d, (e, f)) = ((a, b) % d, c % (e, f)) = ((a % d, b % d), (c % e, c % f)) //Typ zwracanej pary jest wybierany na podstawie typów element operator element. np. // (int, long long) + (long long, unsigned int) = (long long, unsigned long long) // (bitset, int) >> (int, long long) = (bitset, long long) // (string, int) + (char *, double) = (string, double) #define f first #define s second #define vsv sim, class d, class e #define nop(o,c,r,l...) auto operator o(c a, r b)-> decltype(make_pair(l)) {return {l};} //enable_if jest potrzebne tylko, jeśli chcemy mieć operator <<, w przeciwnym wypadku można po prostu: vsv> nop ... #define pcg(o) \ /*para + para*/ vsv, class f> nop(o, pair , pair , a.f o b.f, a.s o b.s) \ /*liczba + para*/ vsv,class = typename enable_if::value>::type> nop(o, c, pair, a o b.f, a o b.s) \ /*para + liczba*/ vsv> nop(o, pair, e, a.f o b, a.s o b) #define clp(o) pcg(o) \ /*para += liczba*/ vsv> void operator o##= (pair & a, e b) {a.f o##= b; a.s o##= b;} \ /*liczba += para*/ vsv, class f> void operator o##= (pair & a, pair b) {a.f o##= b.f; a.s o##= b.s;} #define syd(o) sim, class d> auto operator o(pair e) -> decltype(make_pair(o e.f, o e.s)) {return {o e.f, o e.s};} #define u , //clp: razem z odpowiednim operatorem przypisania, pcg: bez niego, syd: operator jednoargumentowy clp(+) clp(-) clp(*) clp(/) clp(%) clp(^) clp(|) clp(>>) clp(<<) clp(&) pcg(&&) pcg(||) syd(-) syd(+) syd(~) syd(!) #undef u int dist(pii a, pii b) { a -= b; return abs(a.first) + abs(a.second); } void run(pii start, pii end) { for (int i = 1; ; ++i) { pii at = start + i * end; if (get_cell(at) != ' ') { if (get_cell(at) != '*' && get_cell(at) != '#') { debug arr2(board, at.first, at.second) "is iluminated from" imie(start); illuminated[at.first][at.second] = true; } break; } } } int calc(char x) { int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (board[i][j] == x) ans++; return ans; } int calc_with_adj(char me, char oth) { int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (board[i][j] == me) { bool good = false; for (auto [x, y] : vpii{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) if (get_cell(i + x, j + y) == oth) good = true; if (good) ans++; } return ans; } int calc_pairs(char me, char oth) { int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (board[i][j] == me) { for (auto [x, y] : vpii{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) if (get_cell(i + x, j + y) == oth) ans++; } return ans; } bool seen[nax][nax]; void dfs(pii x, const set &allowed, vpii &ans) { if (!allowed.count(get_cell(x))) return; if (seen[x.first][x.second]) return; seen[x.first][x.second] = true; ans.push_back(x); for (auto dx : vpii{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) dfs(x + dx, allowed, ans); } vpii get_component(pii x, const set &allowed) { vpii ans; dfs(x, allowed, ans); return ans; } vpii knight; vpii ferz = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int main() { for (int i : {-2, 2}) for (int j : {-1, 1}) { knight.emplace_back(i, j); knight.emplace_back(j, i); } scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int c; do { c = getchar(); } while (c == '\n'); board[i][j] = c; } } for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) debug arr2(board, i, j); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (get_cell(i, j) == '*') { for (int dx = -1; dx <= 1; ++dx) for (int dy = -1; dy <= 1; ++dy) if (dx || dy) run(pii(i, j), pii(dx, dy)); } int illuminated_count = 0; ll ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) illuminated_count += illuminated[i][j]; debug imie(illuminated_count); ans += illuminated_count * 100; vpii peaks; for (int i = 0; i < n; ++i) for (int j = 0; j + 1 < n; ++j) if (get_cell(i, j) == '/' && get_cell(i, j + 1) == '\\') peaks.emplace_back(i, j); if (peaks.size() >= 2u) { int peak_val = 0; for (auto &x : peaks) { int furthest = 0; for (auto &y : peaks) maxi(furthest, dist(x, y)); peak_val += furthest; } debug imie(peak_val) imie(peak_val * 50); ans += peak_val * 1ll * 50; } int empty_cou = calc(' '); debug imie(empty_cou); ans += empty_cou; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (get_cell(i, j) == '^') { int house_val = 0; for (int ii = i - 1; ii >= 0; --ii) { if (get_cell(ii, j) == ' ') house_val++; else break; } debug imie(i) imie(j) imie(house_val); ans += 5 * house_val; } int min_hg = min(calc('^'), calc('G')); int gd = calc_with_adj('G', 'D'), dg = calc_with_adj('D', 'G'); debug imie(dg) imie(dg); ans += gd * 50; ans += dg * 500; debug imie(min_hg); ans += min_hg * 3; ll a3 = calc('!') * 1ll * calc('v') * 1ll * calc('D'); debug imie(a3); ans += a3; set all_present; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (board[i][j] != ' ') all_present.insert(board[i][j]); int lowest = 1e9; for (char x : all_present) mini(lowest, calc(x)); for (char x : all_present) { int cou = calc(x); if (cou == lowest) ans += cou * 10; } debug imie(lowest); //~ ans += lowest * 10; set uniques; for (int i = 0; i + 3 <= n; ++i) for (int j = 0; j + 3 <= n; ++j) { string x; for (int a = 0; a < 3; ++a) x += string(board[i] + j, board[i] + j + a); uniques.insert(x); } debug imie(uniques.size()); ans += uniques.size(); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (!seen[i][j]) { vpii all = get_component(pii(i, j), set{'D', 'v'}); if (all.empty()) continue; sort(all.begin(), all.end()); int width = 0, curr = 0; for (int l = 0; l < (int) all.size(); ++l) { if (l && all[l - 1] + pii(0, 1) == all[l]) curr++; else { maxi(width, curr); curr = 1; } } maxi(width, curr); debug imie(all) imie(width); ans += width * 500; } int knights = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { pii x = {i, j}; if (get_cell(x) == 'D' || get_cell(x) == 'v') { bool can = false; for (auto n : knight) if (get_cell(x + n) == '!') can = true; if (can) knights++; } } int animals1 = 0; for (char a : string("!vD")) animals1 += calc_pairs(a, ' '); int perimeter = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (board[i][j] == 'v' || board[i][j] == 'D') { pii x = {i, j}; for (auto d : ferz) { int oth = get_cell(x + d); if (oth != 'v' && oth != 'D') perimeter++; } } debug imie(perimeter); ans += perimeter * 60; debug imie(animals1); ans += animals1 * 15; debug imie(knights); ans += knights * 200; memset(seen, 0, sizeof(seen)); int freedom = 0; for (int i = 0; i < n; ++i) for (int j : {0, n - 1}) for (pii x : {pii{i, j}, pii{j, i}}) if (get_cell(x) == ' ') { vpii _; dfs(x, {' '}, _); } for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (board[i][j] != ' ') { pii x = {i, j}; bool is_free = false; for (pii d : ferz) { if (get_cell(d + x) == '#' || seen[(x + d).first][(x + d).second]) is_free = true; } freedom += is_free; } debug imie(freedom); ans += freedom * 7; printf("%lld\n", ans); }