filled_subgrid_count_i_3413.cpp (911B)
1 #include <algorithm> 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 6 void fill(const std::vector<std::vector<char>>& a, 7 std::vector<std::vector<long long>>& t, int i, int j) { 8 if (a[i][j]==a[i][j+1] && a[i][j]==a[i+1][j] && a[i][j]==a[i+1][j+1]) 9 t[i][j] = 1+std::min({t[i+1][j], t[i][j+1], t[i+1][j+1]}); 10 } 11 12 int main() { 13 int n, k; 14 std::string s; 15 std::cin >> n >> k; 16 std::vector<std::vector<char>> a(n, std::vector<char>(n)); 17 std::vector<std::vector<long long>> t(n, std::vector<long long>(n, 1)); 18 for (int i = 0; i < n; i++) { 19 std::cin >> s; 20 for (int j = 0; j < n; j++) 21 a[i][j] = s[j]; 22 } 23 24 for (int d = n-2; d >= 0; d--) { 25 for (int i = d; i >= 0; i--) { 26 fill(a, t, i, d); 27 fill(a, t, d, i); 28 } 29 } 30 31 std::vector<long long> sol(k, 0); 32 for (int i = 0; i < n; i++) 33 for (int j = 0; j < n; j++) 34 sol[a[i][j]-'A'] += t[i][j]; 35 36 for (auto x : sol) 37 std::cout << x << "\n"; 38 }