Advertisement
Guest User

Untitled

a guest
Apr 21st, 2023
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.03 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,unroll-loops")
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cstdint>
  6. #include <cassert>
  7.  
  8. struct Solver
  9. {
  10.     // static variables
  11.     static const int nCols = 31, nRows = 21;
  12.     static const uint64_t INF = ~uint64_t(0);
  13.     // Maze typedef = matrix of booleans:
  14.     // f[r][c] = 1 if it is wall and 0 otherwise
  15.     using Maze = std::vector<std::vector<bool>>;
  16.     // counters for each cell (INF if it is the wall)
  17.     uint64_t map[nRows][nCols];
  18.     // constructor from maze:
  19.     Solver(const Maze &a) { assign(a); }
  20.     // constructor with reading from input stream:
  21.     Solver(std::istream &is, char wall = '#') { read(is, wall); }
  22.    
  23.     void assign(const Maze &a)
  24.     {
  25.         // set the configuration of the maze
  26.         // a[r][c] = 1 if the cell is wall and 0 otherwise
  27.         assert((int)a.size() == nRows);
  28.         for (int r = 0; r < nRows; r++) {
  29.             assert((int)a[r].size() == nCols);
  30.             for (int c = 0; c < nCols; c++)
  31.                 map[r][c] = (a[r][c]?INF:0);
  32.         }
  33.     }
  34.    
  35.     void read(std::istream &is, char wall = '#') {
  36.         for (int r = 0; r < nRows; r++) {
  37.             std::string s; is >> s;
  38.             assert((int)s.size() == nCols);
  39.             for (int c = 0; c < nCols; c++)
  40.                 map[r][c] = (s[c] == wall ? INF : 0);
  41.         }
  42.     }
  43.    
  44.     bool thereIsAPath()
  45.     {
  46.         // check if there is a path from start to finish
  47.         thread_local std::vector<std::pair<int, int>> q;
  48.         q.clear();
  49.         q.push_back({1,1});
  50.         map[1][1] = 1;
  51.         for (int i = 0; i < (int)q.size(); i++)
  52.         {
  53.             auto [r,c] = q[i];
  54.             if (map[r+1][c] == 0) {
  55.                 map[r+1][c] = 1;
  56.                 q.emplace_back(r+1, c);
  57.             }
  58.             if (map[r-1][c] == 0) {
  59.                 map[r-1][c] = 1;
  60.                 q.emplace_back(r-1, c);
  61.             }
  62.             if (map[r][c+1] == 0) {
  63.                 map[r][c+1] = 1;
  64.                 q.emplace_back(r, c+1);
  65.             }
  66.             if (map[r][c-1] == 0) {
  67.                 map[r][c-1] = 1;
  68.                 q.emplace_back(r, c-1);
  69.             }
  70.         }
  71.         bool result = map[nRows-2][nCols-2];
  72.         restore();
  73.         return result;
  74.     }
  75.      
  76.     void restore()
  77.     {
  78.         // revert maze to its initial state
  79.         for (int r = 0; r < nRows; ++r)
  80.             for (int c = 0; c < nCols; ++c)
  81.                 map[r][c] = (map[r][c] == INF) ? INF : 0;
  82.     }
  83.      
  84.     uint64_t count()
  85.     {
  86.         // check if there is a path firstly
  87.         if (!thereIsAPath())
  88.             return INF;
  89.         // start the algorithm of bug's moving:
  90.         int r = 1, c = 1, dir = 0;
  91.         uint64_t answ = 0;
  92.         const int dr[4] = { 1, 0, -1,  0};
  93.         const int dc[4] = { 0, 1,  0, -1};
  94.         do {
  95.             map[r][c]++;
  96.             const auto min1 = std::min(map[r-1][c], map[r+1][c]);
  97.             const auto min2 = std::min(map[r][c-1], map[r][c+1]);
  98.             const auto min = std::min(min1,min2);
  99.             if (map[r+dr[dir]][c+dc[dir]] != min) {
  100.                 for (int next = 0; next < 4; ++next) {
  101.                     if (map[r+dr[next]][c+dc[next]] == min) {
  102.                         dir = next;
  103.                         break;
  104.                     }
  105.                 }
  106.             }
  107.             ++answ;
  108.             r += dr[dir];
  109.             c += dc[dir];
  110.         } while (!(r == nRows-2 && c == nCols-2));
  111.         restore();
  112.         return answ;
  113.     }
  114.    
  115.     Maze getMaze() const
  116.     {
  117.         // this function returns the maze in format 1/0
  118.         Maze f(nRows, std::vector<bool>(nCols));
  119.         for (int r = 0; r < nRows; r++) {
  120.             for (int c = 0; c < nCols; c++) {
  121.                 f[r][c] = (map[r][c] == INF);
  122.             }
  123.         }
  124.         return f;
  125.     }
  126.    
  127. };
  128.  
  129. int main() {
  130.     Solver solver(std::cin, '#');
  131.     if (auto res = solver.count(); res != solver.INF)
  132.         std::cout << res << '\n';
  133.     else
  134.         std::cout << "-1\n";
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement