Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <vector>
       3                 :             : #include <fstream>
       4                 :             : #include <tuple>
       5                 :             : #include <queue>
       6                 :             : #include <set>
       7                 :             : #include <string>
       8                 :             : #include <limits>
       9                 :             : #include <cstdint>
      10                 :             : #include <array>
      11                 :             : 
      12                 :             : using namespace std;
      13                 :             : 
      14                 :             : constexpr array<int_fast8_t, 4> dx{1, 0, -1, 0};
      15                 :             : constexpr array<uint_fast8_t, 2> turnOffsets{1, 3};
      16                 :             : 
      17                 :           2 : int main() {
      18                 :           2 :   ifstream input("input.txt");
      19         [ +  + ]:           2 :   if (!input) {
      20                 :           1 :     cerr << "Error: Could not open input file.\n";
      21                 :           1 :     return 1;
      22                 :             :   }
      23                 :           1 :   vector<string> grid;
      24                 :           1 :   pair<uint_fast16_t, uint_fast16_t> start;
      25                 :           1 :   pair<uint_fast16_t, uint_fast16_t> end;
      26                 :             : 
      27         [ +  + ]:         142 :   for (string line; getline(input, line); grid.push_back(std::move(line))) {
      28         [ +  + ]:       20022 :     for (uint_fast8_t col = 0; col < line.size(); ++col) {
      29         [ +  + ]:       19881 :       if (line[col] == 'S') {
      30                 :           1 :         start = {grid.size(), col};
      31                 :             :       }
      32                 :             :     }
      33                 :           1 :   }
      34                 :             : 
      35                 :           1 :   uint_fast32_t rows = grid.size();
      36                 :           1 :   uint_fast32_t cols = grid[0].size();
      37                 :           1 :   vector visited(rows, vector(cols, vector(4, numeric_limits<uint_fast32_t>::max())));
      38                 :           2 :   vector<vector<vector<vector<tuple<int, int, int>>>>> predecessors(rows, vector<vector<vector<tuple<int, int, int>>>>(cols, vector<vector<tuple<int, int, int>>>(4)));
      39                 :             : 
      40                 :           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<tuple<uint_fast32_t, uint_fast16_t, uint_fast16_t, uint_fast8_t>>> pq;
      41                 :             :     
      42                 :           1 :   pq.emplace(0, start.first, start.second, 0);
      43                 :           1 :   visited[start.first][start.second][0] = 0;
      44                 :             : 
      45         [ +  - ]:       40578 :   while (!pq.empty()) {
      46                 :       40578 :     auto [cost, r, c, dir] = pq.top();
      47                 :       40578 :     pq.pop();
      48                 :             : 
      49         [ +  + ]:       40578 :     if (grid[r][c] == 'E') {
      50                 :           1 :       end = {r, c};
      51                 :           1 :       break;
      52                 :             :     }
      53                 :       40577 :     uint_fast16_t nr = r + dx[(dir + 3) & 3];
      54                 :       40577 :     if (uint_fast16_t nc = c + dx[dir];
      55   [ +  -  +  -  :       40577 :         nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] != '#') {
             +  +  +  + ]
      56         [ +  + ]:       21004 :       if (cost + 1 < visited[nr][nc][dir]) {
      57                 :       11046 :         visited[nr][nc][dir] = cost + 1;
      58                 :       11046 :         pq.emplace(cost + 1, nr, nc, dir);
      59                 :       11046 :         predecessors[nr][nc][dir] = {{r, c, dir}};
      60         [ +  + ]:        9958 :       } else if (cost + 1 == visited[nr][nc][dir]) {
      61                 :         216 :         predecessors[nr][nc][dir].emplace_back(r, c, dir);
      62                 :             :       }
      63                 :             :     }
      64                 :             : 
      65         [ +  + ]:      121731 :     for (uint_fast8_t offset : turnOffsets) {
      66                 :       81154 :       uint_fast8_t newDir = (dir + offset) & 3;
      67         [ +  + ]:       81154 :       if (cost + 1000 < visited[r][c][newDir]) {
      68                 :       29599 :         visited[r][c][newDir] = cost + 1000;
      69                 :       29599 :         pq.emplace(cost + 1000, r, c, newDir);
      70                 :       29599 :         predecessors[r][c][newDir] = {{r, c, dir}};
      71         [ +  + ]:       51555 :       } else if (cost + 1000 == visited[r][c][newDir]) {
      72                 :        9353 :         predecessors[r][c][newDir].emplace_back(r, c, dir);
      73                 :             :       }
      74                 :             :     }
      75                 :             :   }
      76                 :             : 
      77                 :           1 :   set<pair<uint_fast16_t, uint_fast16_t>> unique_tiles;
      78                 :           1 :   queue<tuple<uint_fast16_t, uint_fast16_t, uint_fast8_t>> q;
      79                 :             :     
      80         [ +  + ]:           5 :   for (uint_fast8_t dir = 0; dir < 4; dir++) {
      81         [ +  + ]:           4 :     if (visited[end.first][end.second][dir] != numeric_limits<uint_fast32_t>::max()) {
      82                 :           1 :       q.emplace(end.first, end.second, dir);
      83                 :             :     }
      84                 :             :   }
      85                 :             : 
      86         [ +  + ]:        2842 :   while (!q.empty()) {
      87                 :        2841 :     auto [row, col, direction] = q.front();
      88                 :        2841 :     q.pop();
      89                 :        2841 :     unique_tiles.emplace(row, col);
      90                 :             : 
      91         [ +  + ]:        5681 :     for (const auto& predecessor : predecessors[row][col][direction]) {
      92                 :        2840 :       q.emplace(predecessor);
      93                 :             :     }
      94                 :             :   }
      95                 :             : 
      96                 :           1 :   cout << unique_tiles.size() << endl;
      97         [ +  + ]:           3 : }