Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <string>
       4                 :             : #include <vector>
       5                 :             : #include <array>
       6                 :             : #include <queue>
       7                 :             : #include <iterator>
       8                 :             : 
       9                 :             : using namespace std;
      10                 :             : 
      11                 :             : constexpr array<array<int, 2>, 4> dirs = {{{1,0}, {0,1}, {-1,0}, {0,-1}}};
      12                 :             : 
      13                 :           2 : int main() {
      14                 :           2 :   ifstream input("input.txt");
      15         [ +  + ]:           2 :   if (!input) {
      16                 :           1 :     cerr << "Error: Could not open input file.\n";
      17                 :           1 :     return 1;
      18                 :             :   }
      19                 :           1 :   vector<string> map(istream_iterator<string>(input), {});
      20                 :           1 :   auto rows = static_cast<int>(map.size());
      21                 :           1 :   auto cols = static_cast<int>(map[0].size());
      22                 :           1 :   int totalCost = 0;
      23                 :           1 :   vector<vector<bool>> globalVisited(rows, vector<bool>(cols, false));
      24                 :             : 
      25         [ +  + ]:         141 :   for (int i = 0; i < rows; ++i) {
      26         [ +  + ]:       19740 :     for (int j = 0; j < cols; ++j) {
      27         [ +  + ]:       19600 :       if (!globalVisited[i][j]) {
      28                 :         616 :         vector<vector<bool>> localVisited(rows, vector<bool>(cols, false));
      29                 :         616 :         int minX = i;
      30                 :         616 :         int minY = j;
      31                 :         616 :         int maxX = i;
      32                 :         616 :         int maxY = j;
      33                 :         616 :         int area = 1;
      34                 :         616 :         int sides = 0;
      35                 :         616 :         queue<pair<int, int>> q;
      36                 :         616 :         q.emplace(i, j);
      37                 :         616 :         localVisited[i][j] = globalVisited[i][j] = true;
      38                 :             : 
      39         [ +  + ]:       20216 :         while (!q.empty()) {
      40                 :       19600 :           auto [x, y] = q.front();
      41                 :       19600 :           q.pop();
      42         [ +  + ]:       98000 :           for (const auto& dir : dirs) {
      43                 :       78400 :             int nx = x + dir[0];
      44                 :       78400 :             int ny = y + dir[1];
      45                 :       78400 :             minX = min(minX, nx);
      46                 :       78400 :             maxX = max(maxX, nx);
      47                 :       78400 :             minY = min(minY, ny);
      48                 :       78400 :             maxY = max(maxY, ny);
      49   [ +  +  +  +  :       78400 :             if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && map[nx][ny] == map[i][j] && !localVisited[nx][ny]) {
          +  +  +  +  +  
             +  +  +  +  
                      + ]
      50                 :       18984 :               localVisited[nx][ny] = globalVisited[nx][ny] = true;
      51                 :       18984 :               ++area;
      52                 :       18984 :               q.emplace(nx, ny);
      53                 :             :             }
      54                 :             :           }
      55                 :             :         }
      56                 :             : 
      57         [ +  + ]:        4714 :         for (int x = minX; x < maxX; ++x) {
      58         [ +  + ]:       48977 :           for (int y = minY; y < maxY; ++y) {
      59   [ +  +  +  -  :       44879 :             bool topLeft = x >= 0 && x < rows && y >= 0 && y < cols && localVisited[x][y] && map[x][y] == map[i][j];
          +  +  +  -  +  
                +  +  - ]
      60   [ +  +  +  -  :       44879 :             bool topRight = x >= 0 && x < rows && y+1 >= 0 && y+1 < cols && localVisited[x][y+1] && map[x][y+1] == map[i][j];
          +  -  +  +  +  
                +  +  - ]
      61   [ +  -  +  +  :       44879 :             bool bottomLeft = x+1 >= 0 && x+1 < rows && y >= 0 && y < cols && localVisited[x+1][y] && map[x+1][y] == map[i][j];
          +  +  +  -  +  
                +  +  - ]
      62   [ +  -  +  +  :       44879 :             bool bottomRight = x+1 >= 0 && x+1 < rows && y+1 >= 0 && y+1 < cols && localVisited[x+1][y+1] && map[x+1][y+1] == map[i][j];
          +  -  +  +  +  
                +  +  - ]
      63                 :             :                         
      64                 :       44879 :             int windowSum = topLeft + topRight + bottomLeft + bottomRight;
      65                 :       44879 :             sides += windowSum % 2;
      66         [ +  + ]:       44879 :             if (windowSum == 2) {
      67   [ +  +  +  +  :        6165 :               sides += 2 * ((topLeft && bottomRight) || (bottomLeft && topRight));
             +  +  +  + ]
      68                 :             :             }
      69                 :             :           }
      70                 :             :         }
      71                 :         616 :         totalCost += area * sides;
      72                 :         616 :       }
      73                 :             :     }
      74                 :             :   }
      75                 :           1 :   cout << totalCost << endl;
      76         [ +  + ]:           3 : }