Advertisement
Guest User

Untitled

a guest
Aug 18th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.39 KB | None | 0 0
  1. #include <queue>
  2. #include <tuple>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int mat[1000][1000];
  10. int dist[1000][1000][2];
  11.  
  12. int dx[4] = { 1, -1, 0, 0 };
  13. int dy[4] = { 0, 0, 1, -1 };
  14.  
  15. int main(void) {
  16. ios_base::sync_with_stdio(false);
  17. cin.tie(nullptr);
  18.  
  19. int n, m;
  20. cin >> n >> m;
  21. int sx, sy, ex, ey;
  22. cin >> sx >> sy >> ex >> ey;
  23. sx -= 1;
  24. sy -= 1;
  25. ex -= 1;
  26. ey -= 1;
  27. for (int i = 0; i < n; i++) {
  28. for (int j = 0; j < m; j++) {
  29. cin >> mat[i][j];
  30. }
  31. }
  32.  
  33. memset(dist, -1, sizeof(dist));
  34. queue<tuple<int, int, int>> q;
  35. q.push(make_tuple(sx, sy, 0));
  36. dist[sx][sy][0] = 0;
  37. while (!q.empty()) {
  38. int x, y, z;
  39. tie(x, y, z) = q.front();
  40. q.pop();
  41.  
  42. for (int k = 0; k < 4; k++) {
  43. int tx = x + dx[k];
  44. int ty = y + dy[k];
  45. if (tx < 0 || ty < 0 || tx > n - 1 || ty > m - 1) continue;
  46. if (mat[tx][ty] == 0 && dist[tx][ty][z] == -1) {
  47. dist[tx][ty][z] = dist[x][y][z] + 1;
  48. q.push(make_tuple(tx, ty, z));
  49. }
  50. else if (mat[tx][ty] == 1 && z == 0) {
  51. dist[tx][ty][z + 1] = dist[x][y][z] + 1;
  52. q.push(make_tuple(tx, ty, z + 1));
  53. }
  54. }
  55. }
  56.  
  57. if (dist[ex][ey][0] == -1 && dist[ex][ey][1] == -1) {
  58. cout << "-1\n";
  59. return 0;
  60. }
  61. if (dist[ex][ey][0] == -1) {
  62. cout << dist[ex][ey][1] << '\n';
  63. }
  64. else if (dist[ex][ey][1] == -1) {
  65. cout << dist[ex][ey][0] << '\n';
  66. }
  67. else {
  68. cout << min(dist[ex][ey][0], dist[ex][ey][1]) << '\n';
  69. }
  70.  
  71. return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement