irapilguy

Untitled

Jan 4th, 2018
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <map>
  4. using namespace std;
  5. #define N 110
  6. int labyrinth[N][N];
  7. int n, m;
  8. struct Ver {
  9.     int x, y;
  10.     Ver(int a, int b) {
  11.         x = a;
  12.         y = b;
  13.     }
  14. };
  15. queue<Ver>que;
  16. struct MapCompare
  17. {
  18.     bool operator() (const Ver& a, const Ver& b) const
  19.     {
  20.         return (a.x > b.x) ? (a.x > b.x) : (a.y > b.y);
  21.     }
  22. };
  23.  
  24. map<Ver, int,MapCompare> top;
  25.  
  26. int right(int x,int y) {
  27.     int i = y;
  28.     while (labyrinth[x][i + 1] != 1) {
  29.         i++;
  30.     }
  31.         return i ;
  32. }
  33. int left(int x,int y) {
  34.     int i = y;
  35.     while (labyrinth[x][i - 1] != 1) {
  36.         i--;
  37.     }
  38.      return i ;
  39. }
  40. int up(int x, int y) {
  41.     int i = x;
  42.     while (labyrinth[i-1][y] != 1) {
  43.         i--;
  44.     }
  45.     return i;
  46. }
  47. int down(int x, int y) {
  48.     int i = x;
  49.     while (labyrinth[i+1][y] != 1) {
  50.         i++;
  51.     }
  52.     return i;
  53. }
  54. void bfs(int x, int y) {
  55.     map<Ver, int>::iterator it;
  56.     top.insert(pair<Ver, int> (Ver(x,y), 1));
  57.     que.push(Ver(x, y));
  58.     while (que.size() != 0) {
  59.         int a = que.front().x;
  60.         int b = que.front().y;
  61.         cout << a << " " << b << "\n";
  62.         que.pop();
  63.         it = top.find(Ver(a, b));
  64.         cout << it->second << "\n";
  65.         if (labyrinth[a][b] == 2) {
  66.             cout << it->second;
  67.             return;
  68.         }
  69.         int bend = it->second + 1;
  70.         cout << "ben " << bend << "\n";
  71.         int r = right(a, b);
  72.         cout << "r " << r << "\n";
  73.         if (top.count(Ver(a, r)) != 1) {
  74.             que.push(Ver(a, r));
  75.             cout << "PRIV" << "\n";
  76.             top.insert(pair<Ver, int>(Ver(a, r), bend));
  77.         }
  78.         int l = left(a, b);
  79.         cout << "l " << l << "\n";
  80.         if (top.count(Ver(a, l)) != 1) {
  81.             que.push(Ver(a, l));
  82.             cout << "PRIV" << "\n";
  83.             top.insert(pair<Ver, int>(Ver(a, l), bend));
  84.         }
  85.         int u = up(a, b);
  86.         cout << "u " << u << "\n";
  87.         if (top.count(Ver(u, b)) != 1) {
  88.             que.push(Ver(u, b));
  89.             cout << "priv";
  90.             top.insert(pair<Ver, int>(Ver(u, b), bend));
  91.         }
  92.         int d = down(a, b);
  93.         cout << "d " << d << "\n";
  94.         if (top.count(Ver(d, b)) != 1) {
  95.             que.push(Ver(d, b));
  96.             cout << "priv" << "\n";
  97.             top.insert(pair<Ver, int>(Ver(d, b), bend));
  98.         }
  99.     }
  100.  
  101. }
  102.  
  103. int main() {
  104.     cin >> n >> m;
  105.     for (int i = 1; i <= n ; i++) {
  106.         for (int j = 1; j <= m; j++) {
  107.             cin >> labyrinth[i][j];
  108.         }
  109.     }
  110.     for (int i = 0; i <= m + 1; i++) {
  111.         labyrinth[0][i] = 1;
  112.         labyrinth[n + 1][i] = 1;
  113.     }
  114.     for (int i = 0; i <= n + 1; i++) {
  115.         labyrinth[i][m + 1] = 1;
  116.         labyrinth[i][0] = 1;
  117.     }
  118.     bfs(1, 1);
  119.     return 0;
  120. }
Add Comment
Please, Sign In to add comment