irapilguy

Я смогла написать компаратор , но теперь я не знаю что даль

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