Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <vector>
       4                 :             : #include <string>
       5                 :             : #include <queue>
       6                 :             : #include <array>
       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> grid(istream_iterator<string>(input), {});
      20                 :           2 :   vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size()));
      21                 :           1 :   int total = 0;
      22                 :             : 
      23         [ +  + ]:         141 :   for (int i = 0; i < grid.size(); ++i) {
      24         [ +  + ]:       19740 :     for (int j = 0; j < grid[0].size(); ++j) {
      25         [ +  + ]:       19600 :       if (!visited[i][j]) {
      26                 :         616 :         queue<pair<int, int>> q;
      27                 :         616 :         q.emplace(i, j);
      28                 :         616 :         visited[i][j] = true;
      29                 :         616 :         int area = 1;
      30                 :         616 :         int perimeter = 0;
      31                 :             : 
      32         [ +  + ]:       20216 :         while (!q.empty()) {
      33                 :       19600 :           auto [cx, cy] = q.front();
      34                 :       19600 :           q.pop();
      35         [ +  + ]:       98000 :           for (const auto& dir : dirs) {
      36                 :       78400 :             int nx = cx + dir[0];
      37                 :       78400 :             int ny = cy + dir[1];
      38   [ +  +  +  +  :       78400 :             if (nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size() || grid[nx][ny] != grid[i][j]) {
          +  +  +  +  +  
                +  +  + ]
      39                 :       16820 :               ++perimeter;
      40         [ +  + ]:       61580 :             } else if (!visited[nx][ny]) {
      41                 :       18984 :               visited[nx][ny] = true;
      42                 :       18984 :               ++area;
      43                 :       18984 :               q.emplace(nx, ny);
      44                 :             :             }
      45                 :             :           }
      46                 :             :         }
      47                 :         616 :         total += area * perimeter;
      48                 :         616 :       }
      49                 :             :     }
      50                 :             :   }
      51                 :             : 
      52                 :           1 :   cout << total << endl;
      53         [ +  + ]:           3 : }