Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <string>
       4                 :             : #include <vector>
       5                 :             : #include <array>
       6                 :             : using namespace std;
       7                 :             : 
       8                 :           2 : int main() {
       9                 :           2 :   ifstream inputFile("input.txt");
      10         [ +  + ]:           2 :   if (!inputFile) {
      11                 :           1 :     cerr << "Error opening file." << endl;
      12                 :           1 :     return 1;
      13                 :             :   }
      14                 :             : 
      15                 :           1 :   vector<string> map;
      16                 :           1 :   int startX = 0;
      17                 :           1 :   int startY = 0;
      18                 :             : 
      19         [ +  + ]:         131 :   for (string line; getline(inputFile, line); map.push_back(std::move(line))) {
      20         [ +  + ]:         130 :     if (auto pos = line.find('^'); pos != string::npos) {
      21                 :           1 :       startX = (int)pos; startY = (int)map.size();
      22                 :             :     }
      23                 :           1 :   }
      24                 :             : 
      25                 :           1 :   const auto H = static_cast<int>(map.size());
      26                 :           1 :   const auto W = static_cast<int>(map[0].size());
      27                 :           1 :   constexpr array<array<int_fast8_t, 4>, 2> dOff{{{{-1, 0, 1, 0}}, {{0, 1, 0, -1}}}}; // [dy][dir], [dx][dir]
      28                 :      183508 :   auto id = [W](int x, int y){ return y * W + x; };
      29                 :             : 
      30                 :           1 :   vector<bool> seen(W * H, false);
      31                 :           1 :   vector<tuple<int, int, uint_fast8_t>> candidates;
      32                 :             : 
      33                 :           1 :   int x = startX;
      34                 :           1 :   int y = startY;
      35                 :           1 :   uint_fast8_t direction = 0;
      36                 :           1 :   seen[id(x,y)] = true;
      37                 :             : 
      38                 :             :   while (true) {
      39                 :        5786 :     int nx = x + dOff[1][direction];
      40                 :        5786 :     int ny = y + dOff[0][direction];
      41   [ +  -  +  -  :        5786 :     if (ny < 0 || ny >= H || nx < 0 || nx >= W) {
             +  -  +  + ]
      42                 :             :       break;
      43         [ +  + ]:        5785 :     } else if (map[ny][nx] == '#') {
      44                 :         153 :       direction = (direction + 1) & 3;
      45                 :             :     } else {
      46                 :        5632 :       x = nx; y = ny;
      47                 :        5632 :       int cid = id(x,y);
      48         [ +  + ]:        5632 :       if (!seen[cid]) {
      49                 :        5066 :         seen[cid] = true;
      50                 :        5066 :         candidates.emplace_back(x, y, direction);
      51                 :             :       }
      52                 :             :     }
      53                 :        5785 :   }
      54                 :             : 
      55                 :           1 :   vector<int> stateStamp(W * H * 4, -1);
      56                 :           1 :   int stamp = 0;
      57                 :      177874 :   auto state_key = [&id](int x, int y, int d){ return ((id(x,y) << 2) | d); };
      58                 :             : 
      59                 :           1 :   int endlessLoopCount = 0;
      60                 :             : 
      61         [ +  + ]:        5067 :   for (auto [px, py, dir] : candidates) {
      62                 :        5066 :     direction = dir;
      63                 :             : 
      64                 :             :     // Start from predecessor of the obstacle cell
      65                 :        5066 :     x = px - dOff[1][direction];
      66                 :        5066 :     y = py - dOff[0][direction];
      67                 :             : 
      68                 :        5066 :     ++stamp;
      69                 :             :     while (true) {
      70                 :     6027395 :       int nx = x + dOff[1][direction];
      71                 :     6027395 :       int ny = y + dOff[0][direction];
      72   [ +  +  +  +  :     6027395 :       if (ny < 0 || ny >= H || nx < 0 || nx >= W) {
             +  +  +  + ]
      73                 :             :          break;
      74                 :             :       }
      75   [ +  +  +  +  :     6024122 :       if ((map[ny][nx] == '#') || (nx == px && ny == py)) { // blocked
             +  +  +  + ]
      76                 :      177874 :         direction = (direction + 1) & 3;
      77                 :      177874 :         int key = state_key(x, y, direction);
      78         [ +  + ]:      177874 :         if (stateStamp[key] == stamp) {
      79                 :        1793 :           ++endlessLoopCount;
      80                 :        1793 :           break;
      81                 :             :         }
      82                 :      176081 :         stateStamp[key] = stamp;
      83                 :             :       } else {
      84                 :     5846248 :         x = nx; y = ny;
      85                 :             :       }
      86                 :     6022329 :     }
      87                 :             :   }
      88                 :             : 
      89                 :           1 :   cout << endlessLoopCount << endl;
      90         [ +  + ]:           3 : }