Branch data     Line data    Source code

       1                 :             : #include <unordered_set>
       2                 :             : #include <iostream>
       3                 :             : #include <fstream>
       4                 :             : #include <sstream>
       5                 :             : #include <algorithm>
       6                 :             : #include <array>
       7                 :             : #include <ranges>
       8                 :             : 
       9                 :             : using namespace std;
      10                 :             : 
      11                 :             : constexpr int N = 71;
      12                 :             : constexpr array<int, 4> dx{1, 0, -1, 0};
      13                 :             : constexpr array<int, 4> dy{0, 1, 0, -1};
      14                 :             : 
      15                 :           2 : int main() {
      16                 :           2 :   ifstream input("input.txt");
      17         [ +  + ]:           2 :   if (!input) {
      18                 :           1 :     cerr << "Error: unable to open input.txt" << endl;
      19                 :           1 :     return 1;
      20                 :             :   }
      21                 :             : 
      22                 :           1 :   array<array<bool, N>, N> blocked{};
      23                 :           1 :   array<array<int, N>, N> visitStamp{};
      24                 :           1 :   int bfsRun = 1;
      25                 :           1 :   array<array<int, N>, N> parentX{};
      26                 :           1 :   array<array<int, N>, N> parentY{};
      27                 :           1 :   unordered_set<int> pathCells;
      28                 :           1 :   array<int, N * N> qx{};
      29                 :           1 :   array<int, N * N> qy{};
      30                 :             : 
      31                 :          29 :   auto bfs = [&]() {
      32                 :          29 :     int head = 0;
      33                 :          29 :     int tail = 0;
      34                 :             : 
      35                 :          29 :     qx[tail] = qy[tail++] = 0;
      36                 :          29 :     visitStamp[0][0] = ++bfsRun;
      37                 :          29 :     parentX[0][0] = parentY[0][0] = -1;
      38                 :             : 
      39         [ +  + ]:       81480 :     while (head < tail) {
      40                 :       81479 :       int x = qx[head];
      41                 :       81479 :       int y = qy[head++];
      42   [ +  +  +  + ]:       81479 :       if (x == N - 1 && y == N - 1) {
      43                 :          28 :         pathCells.clear();
      44                 :          28 :         int cy = y;
      45         [ +  + ]:       10638 :         for (int cx = x; cx != -1;) {
      46                 :       10610 :           pathCells.insert(cx * N + cy);
      47                 :       10610 :           tie(cx, cy) = make_pair(parentX[cx][cy], parentY[cx][cy]);
      48                 :             :         }
      49                 :          28 :         return true;
      50                 :             :       }
      51         [ +  + ]:      407255 :       for (int k = 0; k < 4; ++k) {
      52                 :      325804 :         int nx = x + dx[k];
      53                 :      325804 :         int ny = y + dy[k];
      54   [ +  +  +  +  :      325804 :         if (nx >= 0 && ny >= 0 && nx < N && ny < N && !blocked[nx][ny] && visitStamp[nx][ny] != bfsRun) {
          +  +  +  +  +  
             +  +  +  +  
                      + ]
      55                 :       81509 :           visitStamp[nx][ny] = bfsRun;
      56                 :       81509 :           parentX[nx][ny] = x;
      57                 :       81509 :           parentY[nx][ny] = y;
      58                 :       81509 :           qx[tail] = nx;
      59                 :       81509 :           qy[tail++] = ny;
      60                 :             :         }
      61                 :             :       }
      62                 :             :     }
      63                 :           1 :     pathCells.clear();
      64                 :           1 :     return false;
      65                 :           1 :   };
      66                 :             : 
      67                 :           1 :   bfs();
      68                 :             : 
      69                 :           1 :   int x = 0;
      70                 :           1 :   int y = 0;
      71                 :           1 :   int maxCount = 0;
      72                 :           1 :   bool solvable = true;
      73                 :             : 
      74   [ +  -  +  +  :        3015 :   for (string line; getline(input, line) && solvable;) {
                   +  + ]
      75                 :        3014 :     ranges::replace(line, ',', ' ');
      76                 :        3014 :     (stringstream(line) >> x >> y);
      77                 :             : 
      78                 :        3014 :     blocked[x][y] = true;
      79                 :             : 
      80         [ +  + ]:        3014 :     if (++maxCount < 1024) {
      81                 :        1023 :       continue;
      82                 :             :     }
      83                 :             : 
      84         [ +  + ]:        1991 :     if (pathCells.contains(x * N + y)) {
      85                 :          28 :       solvable = bfs();
      86                 :             :     }
      87                 :           1 :   }
      88                 :             : 
      89                 :           1 :   cout << x << ',' << y << endl;
      90         [ +  + ]:           3 : }