fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. struct Point{
  7.     int x, y;
  8. };
  9.  
  10. int W, H;
  11. int maze[202][77];
  12. Point e1, e2;
  13. bool e1f = 0;
  14. queue<Point> Q;
  15. int steps = -1;
  16.  
  17. int main(){
  18.     cin >> W >> H;
  19.     char temp = cin.get();
  20.     for (int i = 0; i < 2*H+1; i++){
  21.         for (int j = 0; j < 2*W+1; j++){
  22.             char c = cin.get();
  23.             if (c == ' ')
  24.                 maze[i][j] = 0;
  25.             else
  26.                 maze[i][j] = -1;
  27.         }
  28.         char temp = cin.get();
  29.     }
  30.  
  31.     for (int w = 1; w < 2*W+1; w+=2){
  32.         if (maze[0][w] == 0){
  33.             if (!e1f){
  34.                 e1.y = 1;
  35.                 e1.x = w;
  36.                 e1f = 1;
  37.             }
  38.             else{
  39.                 e2.y = 1;
  40.                 e2.x = w;
  41.             }
  42.         }
  43.         if (maze[2*H][w] == 0){
  44.             if (!e1f){
  45.                 e1.y = 2*H-1;
  46.                 e1.x = w;
  47.                 e1f = 1;
  48.             }
  49.             else{
  50.                 e2.y = 2*H-1;
  51.                 e2.x = w;
  52.             }
  53.         }
  54.     }
  55.  
  56.     for (int h = 1; h < 2*H+1; h+=2){
  57.         if (maze[h][0] == 0){
  58.             if (!e1f){
  59.                 e1.y = h;
  60.                 e1.x = 1;
  61.                 e1f = 1;
  62.             }
  63.             else{
  64.                 e2.y = h;
  65.                 e2.x = 1;
  66.             }
  67.         }
  68.         if (maze[h][2*W] == 0){
  69.             if (!e1f){
  70.                 e1.y = h;
  71.                 e1.x = 2*W-1;
  72.                 e1f = 1;
  73.             }
  74.             else{
  75.                 e2.y = h;
  76.                 e2.x = 2*W-1;
  77.             }
  78.         }
  79.     }
  80.  
  81.     maze[e1.y][e1.x] = 1;
  82.     Q.push(e1);
  83.  
  84.     while (!Q.empty()){
  85.         Point p = Q.front();
  86.         Q.pop();
  87.         int dya[4] = {-2, 2, 0, 0};
  88.         int dxa[4] = {0, 0, -2, 2};
  89.         for (int i = 0; i < 4; i++){
  90.         	int dy = dya[i];
  91.         	int dx = dxa[i];
  92.             if (p.y + dy > 0 && (p.y + dy < 2*H) &&
  93.                 p.x + dx > 0 && (p.x + dx < 2*W) &&
  94.                 maze[p.y + dy/2][p.x + dx/2] != -1 &&
  95.                 (maze[p.y + dy][p.x + dx] == 0 || maze[p.y + dy][p.x + dx] > maze[p.y][p.x]+1)){
  96.             maze[p.y + dy][p.x + dx] = maze[p.y][p.x] + 1;
  97.             Point k;
  98.             k.y = p.y + dy;
  99.             k.x = p.x + dx;
  100.             Q.push(k);
  101.             }
  102.         }
  103.     }
  104.  
  105.     maze[e2.y][e2.x] = 1;
  106.     Q.push(e2);
  107.  
  108.     while (!Q.empty()){
  109.         Point p = Q.front();
  110.         Q.pop();
  111.         int dya[4] = {-2, 2, 0, 0};
  112.         int dxa[4] = {0, 0, -2, 2};
  113.         for (int i = 0; i < 4; i++){
  114.         	int dy = dya[i];
  115.         	int dx = dxa[i];
  116.             if (p.y + dy > 0 && p.y + dy < 2*H &&
  117.                 p.x + dx > 0 && p.x + dx < 2*W &&
  118.                 maze[p.y + dy/2][p.x + dx/2] != -1 &&
  119.                 (maze[p.y + dy][p.x + dx] == 0 || maze[p.y + dy][p.x + dx] > maze[p.y][p.x]+1)){
  120.             maze[p.y + dy][p.x + dx] = maze[p.y][p.x] + 1;
  121.             Point k;
  122.             k.y = p.y + dy;
  123.             k.x = p.x + dx;
  124.             Q.push(k);
  125.             }
  126.         }
  127.     }
  128.  
  129.     /*for (int i = 0; i < 2*H+1; i++){
  130.         for (int j = 0; j < 2*W+1; j++)
  131.             printf("%3d", maze[i][j]);
  132.         cout << "\n";
  133.     }*/
  134.  
  135.     for (int i = 1; i < 2*H; i+=2){
  136.         for (int j = 1; j < 2*W; j+=2){
  137.             if (maze[i][j] > steps)
  138.                 steps = maze[i][j];
  139.         }
  140.     }
  141.  
  142.     cout << steps << "\n";
  143.  
  144. }
  145.  
Success #stdin #stdout 0s 15304KB
comments (?)
stdin
copy 
5 3
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+
stdout
copy 
9
https://ideone.com/6fcp92
language:
C++ (gcc 8.3)
created:
6 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!