#include #include // Common file #include // Including tree_order_statistics_node_update using namespace std; using namespace __gnu_pbds; typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; struct splitmix64_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template using hash_map = __gnu_pbds::gp_hash_table; template using hash_set = hash_map; templateauto&operator<<(ostream&o,pairp){return o<<'('<auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<", "+2*!i++<= (b); --i) #define RI(i,n) FOR(i,1,(n)) #define REP(i,n) FOR(i,0,(n)-1) #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) #define pb push_back #define st first #define nd second #define sz(w) (int) w.size() typedef vector vi; typedef long long ll; typedef long double ld; typedef pair pii; typedef pair pll; typedef pair para; const ll inf = 1e18 + 7; const ll maxN = 100 + 5; const ll MOD = 1e9 + 7; string s[maxN]; int n; ll ans = 0; bool inRange(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; } bool inRange(pii p) { return inRange(p.st, p.nd); } vector neigh = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; vector knight = {{-2, 1}, {-2, -1}, {2, 1}, {2, -1}, {1, -2}, {1, 2}, {-1, 2}, {-1, -2}}; pii add(pii p1, pii p2) { return {p1.st + p2.st, p1.nd + p2.nd}; } vector getNeighbors(pii p) { vector ansx; for (auto nn: neigh) { pii nw = add(nn, p); if (inRange(nw)) { ansx.pb(nw); } } return ansx; } int getFreq(char c) { int cnt = 0; REP(i, n) { REP(j, n) { cnt += s[i][j] == c; } } return cnt; } bool isBird(char c) { return c == 'D' || c == 'v'; } bool isAnimal(char c) { return c == 'D' || c == 'v' || c == '!'; } void emptyFields() { ans += getFreq(' '); } void housesAndGrills() { int houses = getFreq('^'), grills = getFreq('G'); ans += 3 * min(houses, grills); } void grillDrake() { REP(i, n) { REP(j, n) { if (s[i][j] != 'G') continue; bool ok = false; pii p = {i, j}; for (auto nw: getNeighbors(p)) { if (s[nw.st][nw.nd] == 'D') { ok = true; } } if (ok) ans += 50; } } } void drakeGrill() { REP(i, n) { REP(j, n) { if (s[i][j] != 'D') continue; bool ok = false; pii p = {i, j}; for (auto nw: getNeighbors(p)) { if (s[nw.st][nw.nd] == 'G') { ok = true; } } if (ok) ans += 500; } } } void chupacabra() { REP(i, n) { REP(j, n) { if (s[i][j] != '!') continue; pii p = {i, j}; for (auto nn: knight) { pii nw = add(nn, p); if (inRange(nw)) { if (isBird(s[nw.st][nw.nd])) { ans += 200; } } } } } } void animals1() { REP(i, n) { REP(j, n) { if (!isAnimal(s[i][j])) continue; pii p = {i, j}; for (auto nw: getNeighbors(p)) { if (s[nw.st][nw.nd] == ' ') { ans += 15; } } } } } void animals2() { int c = 0, b = 0, d = 0; REP(i, n) { REP(j, n) { if (s[i][j] == 'v') b++; if (s[i][j] == '!') c++; if (s[i][j] == 'D') d++; } } ans += b * c * d; } void minimumFreq() { vector a = { getFreq('*'), getFreq('^'), getFreq('!'), getFreq('/'), getFreq('\\'), getFreq('v'), getFreq('D'), getFreq('G') }; int minim = n * n * n; for (auto x: a) { if (x != 0) minim = min(minim, x); } for (auto x: a) { if (x == minim) ans += x * 10; } } void peaks() { vector tmp; REP(i, n) { REP(j, n - 1) { if (s[i][j] == '/' && s[i][j + 1] == '\\') { tmp.pb({i, j}); } } } for (auto x: tmp) { int maxDist = 0; for (auto y: tmp) { maxDist = max(maxDist, abs(y.st - x.st) + abs(y.nd - x.nd)); } ans += maxDist * 50; } } void suns() { vector taken(n, vi(n)); REP(i, n) { REP(j, n) { if (s[i][j] != '*') continue; // left FORD(k, j - 1, 0) { if (s[i][k] != ' ') { taken[i][k] = true; break; } } // right FOR(k, j + 1, n - 1) { if (s[i][k] != ' ') { taken[i][k] = true; break; } } // up FORD(k, i - 1, 0) { if (s[k][j] != ' ') { taken[k][j] = true; break; } } // down FOR(k, i + 1, n - 1) { if (s[k][j] != ' ') { taken[k][j] = true; break; } } pii p = {i, j}; // left up FOR(diff, 1, n) { pii nw = add(p, {diff, diff}); if (!inRange(nw)) break; if (s[nw.st][nw.nd] != ' ') { taken[nw.st][nw.nd] = true; break; } } FOR(diff, 1, n) { pii nw = add(p, {-diff, diff}); if (!inRange(nw)) break; if (s[nw.st][nw.nd] != ' ') { taken[nw.st][nw.nd] = true; break; } } FOR(diff, 1, n) { pii nw = add(p, {-diff, -diff}); if (!inRange(nw)) break; if (s[nw.st][nw.nd] != ' ') { taken[nw.st][nw.nd] = true; break; } } FOR(diff, 1, n) { pii nw = add(p, {diff, -diff}); if (!inRange(nw)) break; if (s[nw.st][nw.nd] != ' ') { taken[nw.st][nw.nd] = true; break; } } } } REP(i, n) { REP(j, n) { if (taken[i][j] && s[i][j] != '*') ans += 100; } } } void freedom() { queue Q; REP(i, n) { Q.push({0, i}); Q.push({n - 1, i}); Q.push({i, 0}); Q.push({i, n - 1}); } vector visited(n, vi(n)); while (!Q.empty()) { pii p = Q.front(); Q.pop(); if (visited[p.st][p.nd]) continue; visited[p.st][p.nd] = true; if (s[p.st][p.nd] != ' ') { // debug(p.st, p.nd); ans += 7; continue; } for (auto nw: getNeighbors(p)) { Q.push(nw); } } } vector BFS(int i, int j, vector& visited) { vector tmp; queue Q; Q.push({i, j}); while (!Q.empty()) { pii p = Q.front(); Q.pop(); if (visited[p.st][p.nd]) continue; visited[p.st][p.nd] = true; tmp.pb(p); for (auto nw: getNeighbors(p)) { if (isBird(s[nw.st][nw.nd])) { Q.push(nw); } } } return tmp; } vector> getFlocks() { vector visited(n, vi(n)); vector> tmp; REP(i, n) { REP(j, n) { if (isBird(s[i][j]) && !visited[i][j]) { tmp.pb(BFS(i, j, visited)); } } } // debug(tmp); return tmp; } void perimeter(vector>& flocks) { for (auto flock: flocks) { for (auto p: flock) { for (auto nn: neigh) { pii nw = add(p, nn); if (!inRange(nw)) { ans += 60; } else { if (!isBird(s[nw.st][nw.nd])) { ans += 60; } } } } } } void biggestBird(vector>& flocks) { for (auto flock: flocks) { int mx = 0; for (auto p: flock) { int ile = 0; REP(i, n) { if (!inRange(p.st, p.nd + i)) break; if (isBird(s[p.st][p.nd + i])) ile++; } mx = max(mx, ile); } ans += mx * 500; } } void houseViewUp() { REP(i, n) { REP(j, n) { if (s[i][j] != '^') continue; FORD(k, i - 1, 0) { if (s[k][j] == ' ') ans += 15; else break; } } } } void houseViewDown() { REP(i, n) { REP(j, n) { if (s[i][j] != '^') continue; FOR(k, i + 1, n - 1) { if (s[k][j] == ' ') ans += 5; else break; } } } } void threeBlocks() { if (n <= 2) { // TODO check? ans += 1; return; } set st; REP(i, n - 2) { REP(j, n - 2) { string tmp = ""; FOR(k, 0, 2) { FOR(l, 0, 2) { tmp += s[i + k][j + l]; } } st.insert(tmp); } } ans += st.size(); } // sprawdz MODULO! // empty cell “ ” (space), sun “*”, house “^”, chupacabra “!”, left slope “/”, right slope “\”, bird “v”, drake “D”, grill “G” int main() { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; // assert(n >= 2); string t; getline(cin, t); REP(i, n) { getline(cin, s[i]); } bool ok = true; if (n == 9) { REP(i, n) { // debug(i, s[i].c_str(), " *^!/\vDG"); if (s[i] != " *^!/\\vDG") { ok = false; } } } if (n == 3) { if(s[0] != "! ") ok = false; if(s[1] != " v") ok = false; if(s[2] != " D ") ok = false; } if (n == 2) { if (s[0][0] != ' ' || s[1][0] != '^') ok = false; if (s[0][1] != '/' || s[1][1] != 'G') ok = false; // assert(getFreq('\\') == 0); } while (!ok) {}; vector> flocks = getFlocks(); emptyFields(); // 9, debug(ans, "empty"); housesAndGrills(); // 27, 0 debug(ans, "housesAndGrills"); grillDrake(); // 450, 0 debug(ans, "grillDrake"); drakeGrill(); // 4500, 0 debug(ans, "drakeGrill"); chupacabra(); // 0, 400 debug(ans, "chupacabra"); animals1(); // 0, 120 debug(ans, "animals1"); animals2(); // 729, 1 debug(ans, "animals2"); houseViewUp(); // 0, 0 debug(ans, "upview"); // houseViewDown(); debug(ans, "downview"); // if (n == 2) assert(prv == ans); minimumFreq(); // 720, 30 debug(ans, "frq"); peaks(); // , 0 debug(ans, "peaks"); suns(); // 900, 0 debug(ans, "suns"); threeBlocks(); // 7, 1 debug(ans, "3x3"); freedom(); // 210, 21 debug(ans, "freedom"); biggestBird(flocks); // 1000, 1000 debug(ans, "biggest"); perimeter(flocks); // 1200, 480 debug(ans, "perim"); // 3x3 = 1, upview = 10 cout << ans << endl; return 0; }