fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. const int INF = (int)1e9;
  7.  
  8. struct Solver {
  9.     int nRows;
  10.     int nCols;
  11.     int map[128][128];
  12.  
  13.     Solver(int nRows = 0, int nCols = 0) : nRows(nRows), nCols(nCols) { 
  14.         for (int r = 0; r < nRows; ++r) {
  15.             map[r][0] = map[r][nCols-1] = INF;
  16.         }
  17.  
  18.         for (int c = 0; c < nCols; ++c) {
  19.             map[0][c] = map[nRows-1][c] = INF;
  20.         }
  21.  
  22.         for (int r = 1; r <= nRows-2; ++r) {
  23.             for (int c = 1; c <= nCols-2; ++c) {
  24.                 map[r][c] = 0;
  25.             }
  26.         }
  27.     }    
  28.  
  29.     bool isset_path() {
  30.         std::queue<std::pair<int, int>> q;
  31.         std::vector<std::pair<int, int>> s;
  32.         q.push({1, 1});
  33.         map[1][1] = 1;
  34.         while (!q.empty()) {
  35.             auto curr = q.front(); q.pop(); s.push_back(curr);
  36.             int r = curr.first, c = curr.second;
  37.             if (map[r+1][c] == 0) {
  38.                 map[r+1][c] = 1;
  39.                 q.push({r+1, c});
  40.             }
  41.             if (map[r-1][c] == 0) {
  42.                 map[r-1][c] = 1;
  43.                 q.push({r-1, c});
  44.             }
  45.             if (map[r][c+1] == 0) {
  46.                 map[r][c+1] = 1;
  47.                 q.push({r, c+1});
  48.             }
  49.             if (map[r][c-1] == 0) {
  50.                 map[r][c-1] = 1;
  51.                 q.push({r, c-1});
  52.             }
  53.         }
  54.         bool result = map[nRows-2][nCols-2];
  55.         backup();
  56.         return result;
  57.     }
  58.  
  59.     void backup() {
  60.         for (int r = 0; r < nRows; ++r) {
  61.             for (int c = 0; c < nCols; ++c) {
  62.                 map[r][c] = (map[r][c] == INF) ? INF : 0;
  63.             }
  64.         }
  65.     }
  66.  
  67.     int count() {
  68.         if (!isset_path()) {
  69.             return -1;
  70.         }
  71.         int r = 1, c = 1, dir = 0, answ = 0;
  72.         const int dr[4] = { 1, 0, -1,  0};
  73.         const int dc[4] = { 0, 1,  0, -1};
  74.         do {
  75.             map[r][c]++;
  76.             int min = std::min({map[r-1][c], map[r+1][c], map[r][c+1], map[r][c-1]});
  77.             if (map[r+dr[dir]][c+dc[dir]] != min) {
  78.                 for (int next = 0; next < 4; ++next) {
  79.                     if (map[r+dr[next]][c+dc[next]] == min) {
  80.                         dir = next;
  81.                         break;
  82.                     }
  83.                 }
  84.             }
  85.             ++answ;
  86.             r += dr[dir];
  87.             c += dc[dir];
  88.         } while (!(r == nRows-2 && c == nCols-2));
  89.         backup();
  90.         return answ;
  91.     }
  92.  
  93.     static Solver read() {
  94.         int nRows, nCols;
  95.         scanf("%d %d\n", &nRows, &nCols);
  96.  
  97.         Solver solver(nRows, nCols);
  98.         for (int r = 0; r < nRows; ++r) {
  99.             char buf[101];
  100.             scanf("%[^\n]s", buf); scanf("\n");
  101.             for (int c = 0; c < nCols; ++c) {
  102.                 solver.map[r][c] = (buf[c] == '@') ? INF : 0;
  103.             }
  104.         }
  105.         return solver;
  106.     }
  107. };
  108.  
  109. int main() {
  110.     //freopen("input.txt", "rt", stdin);
  111.     auto solver = Solver::read();
  112.     printf("%d", solver.count());
  113.     return 0;
  114. }
Success #stdin #stdout 0.02s 4536KB
comments (?)
stdin
copy 
21 31
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@         @@   @@ @@ @@  @   @@
@@ @   @ @@          @ @   @  @
@  @   @ @ @ @  @  @     @ @  @
@   @ @@@    @@@@   @@ @ @@ @ @
@  @   @  @ @@   @@@  @ @ @@@ @
@   @ @  @ @@           @  @  @
@  @@ @@     @  @ @ @@@    @@ @
@ @    @@@ @  @  @@@@@@     @ @
@@ @ @    @@ @ @     @      @ @
@     @@@@ @ @ @ @@ @@@   @@  @
@@ @ @     @   @@    @ @ @    @
@  @ @@ @   @  @ @ @@@  @ @  @@
@ @      @ @@@ @   @  @     @ @
@ @@ @@ @@@@@   @@ @     @@   @
@   @ @   @    @    @     @@  @
@      @    @ @    @ @@@    @ @
@ @ @   @ @ @@ @ @     @  @  @@
@@@@     @ @     @   @ @@@ @  @
@@@   @      @ @     @     @@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
stdout
copy 
734938
https://ideone.com/x5Apct
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!