Advertisement
K_Y_M_bl_C

Untitled

Sep 9th, 2017
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. //#define _GLIBCXX_DEBUG
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef vector<int> vi;
  10. typedef long double ld;
  11.  
  12. #define mk make_pair
  13. #define inb push_back
  14. #define X first
  15. #define Y second
  16. #define all(v) v.begin(), v.end()
  17. #define sqr(x) (x) * (x)
  18. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  19. #define y1 AYDARBOG
  20. //continue break pop_back return
  21.  
  22. int solve();
  23.  
  24. int main()
  25. {
  26. //ios_base::sync_with_stdio(0);
  27. //cin.tie(0);
  28. #define TASK "lzss"
  29. #ifndef _DEBUG
  30. //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  31. #endif
  32. solve();
  33. #ifdef _DEBUG
  34. fprintf(stderr, "\nTIME: %.3f\n", TIME);
  35. #endif
  36. }
  37.  
  38. const int BUFSZ = (int)1e5 + 7;
  39. char buf[BUFSZ];
  40. string get_str()
  41. {
  42. scanf(" %s", buf);
  43. return string(buf);
  44. }
  45.  
  46. int solve()
  47. {
  48. int n, m;
  49. scanf("%d %d", &n, &m);
  50. swap(n, m);
  51. vector<vi> h(n, vi(m));
  52. pii st, fn;
  53. scanf("%d %d", &st.Y, &st.X);
  54. --st.Y, --st.X;
  55. scanf("%d %d", &fn.Y, &fn.X);
  56. --fn.Y, --fn.X;
  57. for (int i = 0; i < n; ++i)
  58. {
  59. for (int j = 0; j < m; ++j)
  60. {
  61. scanf("%d", &h[i][j]);
  62. }
  63. }
  64. vector<vi> d(n, vi(m, -1));
  65. d[st.X][st.Y] = 0;
  66. queue<pii> q;
  67. q.push(st);
  68. while (!q.empty())
  69. {
  70. int x = q.front().X;
  71. int y = q.front().Y;
  72. q.pop();
  73. //horr
  74. {
  75. int ch = h[x][y] + 1;
  76. int nx = x;
  77. int ny = y + 1;
  78. while (ny < m)
  79. {
  80. if (ch >= h[nx][ny])
  81. {
  82. if (d[nx][ny] == -1)
  83. {
  84. d[nx][ny] = d[x][y] + 1;
  85. q.push(mk(nx, ny));
  86. }
  87. }
  88. else
  89. {
  90. break;
  91. }
  92. ++ny;
  93. --ch;
  94. }
  95. }
  96. //horl
  97. {
  98. int ch = h[x][y] + 1;
  99. int nx = x;
  100. int ny = y - 1;
  101. while (ny >= 0)
  102. {
  103. if (ch >= h[nx][ny])
  104. {
  105. if (d[nx][ny] == -1)
  106. {
  107. d[nx][ny] = d[x][y] + 1;
  108. q.push(mk(nx, ny));
  109. }
  110. }
  111. else
  112. {
  113. break;
  114. }
  115. --ny;
  116. --ch;
  117. }
  118. }
  119. //veru
  120. {
  121. int ch = h[x][y] + 1;
  122. int nx = x - 1;
  123. int ny = y;
  124. while (nx >= 0)
  125. {
  126. if (ch >= h[nx][ny])
  127. {
  128. if (d[nx][ny] == -1)
  129. {
  130. d[nx][ny] = d[x][y] + 1;
  131. q.push(mk(nx, ny));
  132. }
  133. }
  134. else
  135. {
  136. break;
  137. }
  138. --nx;
  139. --ch;
  140. }
  141. }
  142. //verd
  143. {
  144. int ch = h[x][y] + 1;
  145. int nx = x + 1;
  146. int ny = y;
  147. while (nx < n)
  148. {
  149. if (ch >= h[nx][ny])
  150. {
  151. if (d[nx][ny] == -1)
  152. {
  153. d[nx][ny] = d[x][y] + 1;
  154. q.push(mk(nx, ny));
  155. }
  156. }
  157. else
  158. {
  159. break;
  160. }
  161. ++nx;
  162. --ch;
  163. }
  164. }
  165. }
  166. if (d[fn.X][fn.Y] == -1)
  167. puts("IMPOSSIBLE"), exit(0);
  168. printf("%d\n", d[fn.X][fn.Y]);
  169. return 0;
  170. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement