Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast,unroll-loops")
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cstdint>
- #include <cassert>
- struct Solver
- {
- // static variables
- static const int nCols = 31, nRows = 21;
- static const uint64_t INF = ~uint64_t(0);
- // Maze typedef = matrix of booleans:
- // f[r][c] = 1 if it is wall and 0 otherwise
- using Maze = std::vector<std::vector<bool>>;
- // counters for each cell (INF if it is the wall)
- uint64_t map[nRows][nCols];
- // constructor from maze:
- Solver(const Maze &a) { assign(a); }
- // constructor with reading from input stream:
- Solver(std::istream &is, char wall = '#') { read(is, wall); }
- void assign(const Maze &a)
- {
- // set the configuration of the maze
- // a[r][c] = 1 if the cell is wall and 0 otherwise
- assert((int)a.size() == nRows);
- for (int r = 0; r < nRows; r++) {
- assert((int)a[r].size() == nCols);
- for (int c = 0; c < nCols; c++)
- map[r][c] = (a[r][c]?INF:0);
- }
- }
- void read(std::istream &is, char wall = '#') {
- for (int r = 0; r < nRows; r++) {
- std::string s; is >> s;
- assert((int)s.size() == nCols);
- for (int c = 0; c < nCols; c++)
- map[r][c] = (s[c] == wall ? INF : 0);
- }
- }
- bool thereIsAPath()
- {
- // check if there is a path from start to finish
- thread_local std::vector<std::pair<int, int>> q;
- q.clear();
- q.push_back({1,1});
- map[1][1] = 1;
- for (int i = 0; i < (int)q.size(); i++)
- {
- auto [r,c] = q[i];
- if (map[r+1][c] == 0) {
- map[r+1][c] = 1;
- q.emplace_back(r+1, c);
- }
- if (map[r-1][c] == 0) {
- map[r-1][c] = 1;
- q.emplace_back(r-1, c);
- }
- if (map[r][c+1] == 0) {
- map[r][c+1] = 1;
- q.emplace_back(r, c+1);
- }
- if (map[r][c-1] == 0) {
- map[r][c-1] = 1;
- q.emplace_back(r, c-1);
- }
- }
- bool result = map[nRows-2][nCols-2];
- restore();
- return result;
- }
- void restore()
- {
- // revert maze to its initial state
- for (int r = 0; r < nRows; ++r)
- for (int c = 0; c < nCols; ++c)
- map[r][c] = (map[r][c] == INF) ? INF : 0;
- }
- uint64_t count()
- {
- // check if there is a path firstly
- if (!thereIsAPath())
- return INF;
- // start the algorithm of bug's moving:
- int r = 1, c = 1, dir = 0;
- uint64_t answ = 0;
- const int dr[4] = { 1, 0, -1, 0};
- const int dc[4] = { 0, 1, 0, -1};
- do {
- map[r][c]++;
- const auto min1 = std::min(map[r-1][c], map[r+1][c]);
- const auto min2 = std::min(map[r][c-1], map[r][c+1]);
- const auto min = std::min(min1,min2);
- if (map[r+dr[dir]][c+dc[dir]] != min) {
- for (int next = 0; next < 4; ++next) {
- if (map[r+dr[next]][c+dc[next]] == min) {
- dir = next;
- break;
- }
- }
- }
- ++answ;
- r += dr[dir];
- c += dc[dir];
- } while (!(r == nRows-2 && c == nCols-2));
- restore();
- return answ;
- }
- Maze getMaze() const
- {
- // this function returns the maze in format 1/0
- Maze f(nRows, std::vector<bool>(nCols));
- for (int r = 0; r < nRows; r++) {
- for (int c = 0; c < nCols; c++) {
- f[r][c] = (map[r][c] == INF);
- }
- }
- return f;
- }
- };
- int main() {
- Solver solver(std::cin, '#');
- if (auto res = solver.count(); res != solver.INF)
- std::cout << res << '\n';
- else
- std::cout << "-1\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement