Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <vector>
       4                 :             : #include <queue>
       5                 :             : #include <limits>
       6                 :             : #include <string>
       7                 :             : #include <tuple>
       8                 :             : #include <cstdint>
       9                 :             : #include <array>
      10                 :             : 
      11                 :             : using namespace std;
      12                 :             : 
      13                 :             : constexpr array<array<int, 2>, 4> directions{{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}};
      14                 :             : constexpr std::array<uint_fast8_t, 2> turnOffsets{1, 3};
      15                 :             : 
      16                 :           2 : int main() {
      17                 :           2 :   ifstream input("input.txt");
      18         [ +  + ]:           2 :   if (!input) {
      19                 :           1 :     cerr << "Error: Could not open input file.\n";
      20                 :           1 :     return 1;
      21                 :             :   }
      22                 :           1 :   vector<string> grid;
      23                 :           1 :   pair<uint_fast16_t, uint_fast16_t> start;
      24                 :             : 
      25         [ +  + ]:         142 :   for (string line; getline(input, line); grid.push_back(std::move(line))) {
      26         [ +  + ]:         141 :     if (auto pos = line.find('S'); pos != string::npos) {
      27                 :           1 :       start = {pos, grid.size()};
      28                 :             :     }
      29                 :           1 :   }
      30                 :             : 
      31                 :           1 :   uint_fast16_t rows = grid.size();
      32                 :           1 :   uint_fast16_t cols = grid[0].size();
      33                 :           1 :   vector<uint_fast32_t> visited(rows * cols * 4, numeric_limits<uint_fast32_t>::max());
      34                 :             : 
      35                 :           1 :   priority_queue<tuple<uint_fast32_t, uint_fast16_t, uint_fast16_t, uint_fast8_t>, vector<tuple<uint_fast32_t, uint_fast16_t, uint_fast16_t, uint_fast8_t>>, greater<>> pq;
      36                 :             : 
      37                 :           1 :   pq.emplace(0, start.first, start.second, 0);
      38                 :           1 :   visited[(start.second * cols + start.first) * 4 + 0] = 0;
      39                 :             : 
      40         [ +  - ]:       40578 :   while (!pq.empty()) {
      41                 :       40578 :     auto [cost, x, y, direction] = pq.top();
      42                 :       40578 :     pq.pop();
      43         [ +  + ]:       40578 :     if (grid[y][x] == 'E') {
      44                 :           1 :       cout << cost << endl;
      45                 :           1 :       break;
      46                 :             :     }
      47                 :             : 
      48                 :       40577 :     uint_fast16_t newX = x + directions[direction][0];
      49                 :       40577 :     uint_fast16_t newY = y + directions[direction][1];
      50                 :       40577 :     if (auto& currentVisited = visited[(newY * cols + newX) * 4 + direction];
      51   [ +  -  +  -  :       40577 :         newX < cols && newY < rows && grid[newY][newX] != '#' && cost + 1 < currentVisited) {
          +  +  +  +  +  
                      + ]
      52                 :       11046 :       currentVisited = cost + 1;
      53                 :       11046 :       pq.emplace(cost + 1, newX, newY, direction);
      54                 :             :     }
      55                 :             : 
      56         [ +  + ]:      121731 :     for (uint_fast8_t offset : turnOffsets) {
      57                 :       81154 :       auto nd = (direction + offset) & 3;
      58                 :       81154 :       auto& turnedVisited = visited[(y * cols + x) * 4 + nd];
      59         [ +  + ]:       81154 :       if (cost + 1000 < turnedVisited) {
      60                 :       29599 :         turnedVisited = cost + 1000;
      61                 :       29599 :         pq.emplace(cost + 1000, x, y, nd);
      62                 :             :       }
      63                 :             :     }
      64                 :             :   }
      65         [ +  + ]:           3 : }