achulkov2

Untitled

Apr 17th, 2018
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4.  
  5. using namespace std;
  6.  
  7. const int INF = 10000000;
  8.  
  9. int h, w;
  10. vector<vector<int>> field;
  11. vector<pair<int, int>> steps;
  12. vector<vector<vector<int>>> dist;
  13. deque<pair<pair<int, int>, int>> q;
  14.  
  15. bool ok(int xh, int xw) {
  16. return 0 <= xh && xh < h && 0 <= xw && xw < w && field[xh][xw];
  17. }
  18.  
  19. void bfs(int xh, int xw) {
  20. dist.assign(h, vector<vector<int>>(w, vector<int>(8, INF)));
  21. q.clear();
  22. for (int dir = 0; dir < 8; ++dir) {
  23. q.push_back({{xh, xw}, dir});
  24. dist[xh][xw][dir] = 1;
  25. }
  26. while (!q.empty()) {
  27. auto v = *q.begin();
  28. q.pop_front();
  29. int vh = v.first.first, vw = v.first.second, v_dir = v.second;
  30. for (int i = 0; i < 8; ++i) {
  31. int nh = vh + steps[i].first, nw = vw + steps[i].second;
  32. if (ok(nh, nw) && dist[nh][nw][i] > dist[vh][vw][v_dir] + (i != v_dir)) {
  33. dist[nh][nw][i] = dist[vh][vw][v_dir] + (i != v_dir);
  34. if (i == v_dir) {
  35. q.push_front({{nh, nw}, i});
  36. } else {
  37. q.push_back({{nh, nw}, i});
  38. }
  39. }
  40. }
  41. }
  42. }
  43.  
  44. int main() {
  45. cin >> h >> w;
  46. field.assign(h, vector<int>(w, 0));
  47. for (int i = 0; i < h; ++i) {
  48. for (int j = 0; j < w; ++j) {
  49. char c;
  50. cin >> c;
  51. if (c == '.') {
  52. field[i][j] = 1;
  53. }
  54. }
  55. }
  56. int sh, sw, th, tw;
  57. cin >> sw >> sh >> tw >> th;
  58. --sw;
  59. sh = h - sh;
  60. --tw;
  61. th = h - th;
  62. for (int dh = -1; dh <= 1; ++dh) {
  63. for (int dw = -1; dw <= 1; ++dw) {
  64. if (dh != 0 || dw != 0) {
  65. steps.push_back({dh, dw});
  66. }
  67. }
  68. }
  69. int best = INF;
  70. bfs(sh, sw);
  71. for (int t_dir = 0; t_dir < 8; ++t_dir) {
  72. best = min(best, dist[th][tw][t_dir]);
  73. }
  74. if (best == INF) {
  75. cout << "-1\n";
  76. } else {
  77. cout << best << "\n";
  78. }
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment