_takumi

dp

Mar 15th, 2023
728
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4.  
  5. int main() {
  6.     int n, m;
  7.     std::cin >> n >> m;
  8.     std::vector<std::vector<char>> v(n, std::vector<char>(m));
  9.     for (int i = 0; i < n; ++i) {
  10.         for (int j = 0; j < m; ++j) {
  11.             std::cin >> v[i][j];
  12.         }
  13.     }
  14.     std::vector<std::vector<int>> v1(n, std::vector<int>(m, 0));
  15.     std::vector<std::vector<int>> v2(n, std::vector<int>(m, 0));
  16.     std::vector<std::vector<int>> v3(n, std::vector<int>(m, 0));
  17.     std::vector<std::vector<int>> v4(n, std::vector<int>(m, 0));
  18.  
  19.  
  20.     for (int i = 1; i < n; ++i) {
  21.         for (int j = 1; j < m; ++j) {
  22.             if (v[i - 1][j] == v[i][j] && v[i][j - 1] == v[i][j]) { //    |
  23.                 v1[i][j] = 1 + std::min(v1[i - 1][j], v1[i][j - 1]);//  ---
  24.             }
  25.         }
  26.     }
  27.  
  28.     for (int i = 1; i < n; ++i) {
  29.         for (int j = 0; j < m - 1; ++j) {
  30.             if (v[i - 1][j] == v[i][j] && v[i][j + 1] == v[i][j]) { // |
  31.                 v2[i][j] = 1 + std::min(v2[i - 1][j], v2[i][j + 1]);// ---
  32.             }
  33.         }
  34.     }
  35.  
  36.     for (int i = 0; i < n - 1; ++i) {
  37.         for (int j = 0; j < m - 1; ++j) {
  38.             if (v[i + 1][j] == v[i][j] && v[i][j + 1] == v[i][j]) { // ---
  39.                 v3[i][j] = 1 + std::min(v3[i + 1][j], v3[i][j + 1]);// |
  40.             }
  41.         }
  42.     }
  43.  
  44.     for (int i = 0; i < n - 1; ++i) {
  45.         for (int j = 1; j < m; ++j) {
  46.             if (v[i + 1][j] == v[i][j] && v[i][j - 1] == v[i][j]) { // ---
  47.                 v4[i][j] = 1 + std::min(v4[i + 1][j], v4[i][j - 1]);//   |
  48.             }
  49.         }
  50.     }
  51.     int ans = n * m;
  52.     for (int i = 1; i < n - 1; ++i) {
  53.         for (int j = 1; j < m - 1; ++j) {
  54.             ans += std::min(std::min(v1[i][j], v2[i][j]), std::min(v3[i][j], v4[i][j]));
  55.         }
  56.     }
  57.     std::cout << ans << std::endl;
  58.     return 0;
  59. }
  60.  
Advertisement
Add Comment
Please, Sign In to add comment