irapilguy

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

Dec 29th, 2017
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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