Branch data     Line data    Source code

       1                 :             : #include <array>
       2                 :             : #include <iostream>
       3                 :             : #include <fstream>
       4                 :             : #include <vector>
       5                 :             : #include <queue>
       6                 :             : #include <string>
       7                 :             : 
       8                 :             : using namespace std;
       9                 :             : 
      10                 :             : static constexpr std::array<std::array<int, 2>, 4> kCardinalOffsets{{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}};
      11                 :             : 
      12                 :           2 : int main() {
      13                 :           2 :   ifstream input("input.txt");
      14         [ +  + ]:           2 :   if (!input) {
      15                 :           1 :       cerr << "Error: input.txt not found or inaccessible." << endl;
      16                 :           1 :       return 1;
      17                 :             :   }
      18                 :             : 
      19                 :           1 :   vector<vector<char>> grid;
      20                 :           1 :   vector<pair<int, int>> zeroPositions;
      21                 :           1 :   queue<pair<int, int>> q;
      22   [ +  +  +  -  :          57 :   for (string line; getline(input, line) && !line.empty(); grid.emplace_back(line.begin(), line.end())) {
                   +  + ]
      23         [ +  + ]:        3192 :     for (int i = 0; i < line.size(); ++i) {
      24         [ +  + ]:        3136 :       if (line[i] == '0') {
      25                 :         296 :         zeroPositions.emplace_back(i, grid.size());
      26                 :         296 :         q.push({i, grid.size()});
      27                 :             :       }
      28                 :             :     }
      29                 :           1 :   }
      30                 :             : 
      31                 :           1 :   int totalWays = 0;
      32                 :           1 :   auto rows = static_cast<int>(grid.size());
      33                 :           1 :   auto cols = static_cast<int>(grid[0].size());
      34                 :           1 :   vector<vector<int>> ways(rows, vector<int>(cols, 0)); // DP table to store path counts
      35                 :             : 
      36         [ +  + ]:         297 :   for (auto [x, y] : zeroPositions) {
      37                 :         296 :     ways[y][x] = 1; // Each '0' starts with 1 path
      38                 :             :   }
      39                 :             : 
      40         [ +  + ]:        2919 :   while (!q.empty()) {
      41                 :        2918 :     auto [currentX, currentY] = q.front();
      42                 :        2918 :     q.pop();
      43                 :             : 
      44         [ +  + ]:        2918 :     if (grid[currentY][currentX] == '9') {
      45                 :         247 :         totalWays += ways[currentY][currentX];
      46                 :         247 :         continue;
      47                 :             :     }
      48                 :             : 
      49         [ +  + ]:       13355 :     for (const auto& [dx, dy] : kCardinalOffsets) {
      50                 :       10684 :       int neighborX = currentX + dx;
      51                 :       10684 :       int neighborY = currentY + dy;
      52   [ +  +  +  +  :       10684 :       if (neighborX >= 0 && neighborX < cols && neighborY >= 0 && neighborY < rows && grid[neighborY][neighborX] == grid[currentY][currentX] + 1) {
          +  +  +  +  +  
                +  +  + ]
      53         [ +  + ]:        3239 :         if (ways[neighborY][neighborX] == 0) {
      54                 :        2622 :           q.push({neighborX, neighborY}); // First visit
      55                 :             :         }
      56                 :        3239 :         ways[neighborY][neighborX] += ways[currentY][currentX];
      57                 :             :       }
      58                 :             :     }
      59                 :             :   }
      60                 :             : 
      61                 :           1 :   cout << totalWays << endl;
      62         [ +  + ]:           3 : }