fork(1) download 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. enum e_state
  6. {
  7.     SAFETY = 0,
  8.     DANGER,
  9.     DEATH,
  10. };
  11.  
  12. #define MAP_MAX 500
  13.  
  14. int _map[MAP_MAX + 1][MAP_MAX + 1] = {SAFETY, };
  15. int num_danger, num_death;
  16. int dx[4] = {-1, 1, 0, 0};
  17. int dy[4] = {0, 0, 1, -1};
  18.  
  19. struct Info
  20. {
  21.     int x, y;
  22.     int lost_life;
  23.  
  24.     Info(int x_, int y_, int lost_life_) : x(x_), y(y_), lost_life(lost_life_) {}
  25. };
  26.  
  27. #include <queue>
  28. int visit[MAP_MAX + 1][MAP_MAX + 1];
  29.  
  30. #define TEST_MAX 10
  31. void printMap()
  32. {
  33.     cout << "==map==\n";
  34.     for (int y = 0; y <= TEST_MAX; ++y)
  35.     {
  36.         for (int x = 0; x <= TEST_MAX; ++x)
  37.         {
  38.             cout << _map[y][x];
  39.         }
  40.         cout << '\n';
  41.     }
  42.  
  43.     cout << "==visit==\n";
  44.     for (int y = 0; y <= TEST_MAX; ++y)
  45.     {
  46.         for (int x = 0; x <= TEST_MAX; ++x)
  47.         {
  48.             cout << visit[y][x];
  49.         }
  50.         cout << '\n';
  51.     }
  52. }
  53.  
  54. void output()
  55. {
  56.     long long res = -1;
  57.     queue<Info> q;
  58.  
  59.     visit[0][0] = 1;
  60.     Info start(0, 0, 0);
  61.     q.push(start);
  62.  
  63.     while (!q.empty())
  64.     {
  65.         Info tmp = q.front();
  66.         q.pop();
  67.  
  68.         if (tmp.x == MAP_MAX && tmp.y == MAP_MAX)
  69.         {
  70.             if (res == -1 || tmp.lost_life < res)
  71.                 res = tmp.lost_life;
  72.             continue;
  73.         }
  74.  
  75.         for (int i = 0; i < 4; i++)
  76.         {
  77.             int nx = tmp.x + dx[i];
  78.             int ny = tmp.y + dy[i];
  79.             if (nx >= 0 && ny >= 0 && nx <= MAP_MAX && ny <= MAP_MAX && visit[ny][nx] == 0 && _map[ny][nx] != DEATH)
  80.             {
  81.                 visit[ny][nx] = 1;
  82.                 int lost_life = tmp.lost_life;
  83.                 if (_map[ny][nx] == DANGER)
  84.                     lost_life += 1;
  85.                 q.push(Info(nx, ny, lost_life));
  86.             }
  87.         }
  88.     }
  89.  
  90.     cout << res;
  91. }
  92.  
  93. void setMap(int x_start, int y_start, int x_end, int y_end, e_state state)
  94. {
  95.     for (int y = y_start; y <= y_end; ++y)
  96.     {
  97.         for (int x = x_start; x <= x_end; ++x)
  98.         {
  99.             _map[y][x] = state;
  100.         }
  101.     }
  102. }
  103.  
  104. void input()
  105. {
  106.     cin >> num_danger;
  107.     for (int i = 0; i < num_danger; ++i)
  108.     {
  109.         int x1, y1, x2, y2;
  110.         // cin >> x1 >> y1 >> x2 >> y2;
  111.         cin >> y1 >> x1 >> y2 >> x2;
  112.         setMap(min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2), DANGER);
  113.     }
  114.     cin >> num_death;
  115.     for (int i = 0; i < num_death; ++i)
  116.     {
  117.         int x1, y1, x2, y2;
  118.         // cin >> x1 >> y1 >> x2 >> y2;
  119.         cin >> y1 >> x1 >> y2 >> x2;
  120.         setMap(min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2), DEATH);
  121.     }
  122. }
  123.  
  124.  
  125. int main()
  126. {
  127.     input();
  128.     output();
  129. }
  130.  
  131.     // printMap();
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin 
1
0 0 499 500
0
stdout 
999
https://ideone.com/pj9k0L
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

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!