Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <vector>
       4                 :             : #include <string>
       5                 :             : #include <array>
       6                 :             : #include <unordered_map>
       7                 :             : 
       8                 :             : using namespace std;
       9                 :             : 
      10                 :             : constexpr array<array<int, 2>, 4> directions = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      11                 :             : constexpr array<int, 3> turnOffsets{0, 1, 3};
      12                 :             : constexpr int maximumCheatDistance = 20;
      13                 :             : constexpr int savingsWanted = 100;
      14                 :             : 
      15                 :           2 : int main() {
      16                 :           2 :   ifstream input("input.txt");
      17         [ +  + ]:           2 :   if (!input) {
      18                 :           1 :     cerr << "Error: Could not open input file.\n";
      19                 :           1 :     return 1;
      20                 :             :   }
      21                 :           1 :   vector<string> grid;
      22                 :           1 :   pair<int, int> pos;
      23                 :             :     
      24         [ +  + ]:         142 :   for (string line; getline(input, line); grid.push_back(std::move(line))) {
      25         [ +  + ]:       20022 :     for (int col = 0; col < line.size(); ++col) {
      26         [ +  + ]:       19881 :       if (line[col] == 'S') {
      27                 :           1 :         pos = {grid.size() , col};
      28                 :             :       }
      29                 :             :     }
      30                 :           1 :   }
      31                 :             : 
      32                 :           1 :   vector<pair<int, int>> path;
      33                 :           1 :   vector<int> locIndex(grid.size() * grid[0].size(), -1);
      34                 :           1 :   int direction = 0;
      35                 :           1 :   int idx = 0;
      36                 :        9389 :   auto encode = [&grid](pair<int, int> cell) { return cell.first * grid[0].size() + cell.second; };
      37                 :             : 
      38         [ +  + ]:        9389 :   while (grid[pos.first][pos.second] != 'E') {
      39                 :        9388 :     path.push_back(pos);
      40                 :        9388 :     locIndex[ encode(pos) ] = idx++;
      41                 :             :         
      42         [ +  - ]:       13855 :     for (int offset : turnOffsets) {
      43                 :       13855 :       int d = (direction + offset) & 3;
      44                 :       13855 :       int nx = pos.first + directions[d][0];
      45                 :       13855 :       int ny = pos.second + directions[d][1];
      46   [ +  -  +  -  :       13855 :       if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] != '#') {
          +  -  +  -  +  
                +  +  + ]
      47                 :        9388 :         pos = {nx, ny};
      48                 :        9388 :         direction = d;
      49                 :        9388 :         break;
      50                 :             :       }
      51                 :             :     }
      52                 :             :   }
      53                 :           1 :   path.push_back(pos); // add end
      54                 :           1 :   locIndex[ encode(pos) ] = idx;
      55                 :             : 
      56                 :           1 :   long long validCheats = 0;
      57         [ +  + ]:        9390 :   for (int i = 0; i < (int)path.size(); ++i) {
      58                 :        9389 :     auto [x, y] = path[i];
      59         [ +  + ]:      394338 :     for (int dx = -maximumCheatDistance; dx <= maximumCheatDistance; ++dx) {
      60         [ +  + ]:    16167858 :       for (int dy = -maximumCheatDistance; dy <= maximumCheatDistance; ++dy) {
      61                 :    15782909 :         int D = abs(dx) + abs(dy);
      62         [ +  + ]:    15782909 :         if (D > maximumCheatDistance) {
      63                 :     7886760 :           continue;
      64                 :             :         }
      65                 :             : 
      66                 :     7896149 :         int nx = x + dx;
      67                 :     7896149 :         int ny = y + dy;
      68   [ +  +  +  +  :     7896149 :         if (nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size()) {
          +  +  +  +  +  
                      + ]
      69                 :      696997 :           continue;
      70                 :             :         }
      71                 :             : 
      72                 :     7199152 :         int key = nx * grid[0].size() + ny;
      73         [ +  + ]:     7199152 :         if (locIndex[key] >= i + savingsWanted + D) {
      74                 :     1006101 :           ++validCheats;
      75                 :             :         }
      76                 :             :       }
      77                 :             :     }
      78                 :             :   }
      79                 :             : 
      80                 :           1 :   cout << validCheats << endl;
      81         [ +  + ]:           3 : }