Advertisement
Guest User

Untitled

a guest
Jan 18th, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.72 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. #define MAX 1002
  7.  
  8. using namespace std;
  9.  
  10. bool matrix[MAX][MAX];
  11. vector<pair<int, int>> path;
  12.  
  13. int w, h, x1, y1, x2, y2;
  14.  
  15. bool dfs(int x, int y) {
  16. if (x == x2 && y == y2) {return 1;} // if v == goal
  17. matrix[x][y] = 0;
  18. if(matrix[x + 1][y] != 0)
  19. if (dfs(x+1,y)) {path.push_back({x + 1, y}) ; return 1; }
  20. if(matrix[x - 1][y] != 0)
  21. if (dfs(x-1,y)) {path.push_back({x - 1, y}) ; return 1; }
  22. if(matrix[x][y + 1] != 0)
  23. if (dfs(x,y + 1)) {path.push_back({x, y + 1}) ; return 1; }
  24. if(matrix[x][y - 1] != 0)
  25. if (dfs(x,y - 1)) {path.push_back({x, y - 1}) ; return 1; }
  26. return 0;
  27. }
  28.  
  29. int main() {
  30. cin >> w >> h;
  31. cin >> x1 >> y1;
  32. cin >> x2 >> y2;
  33.  
  34. char symb;
  35.  
  36. for(int i = 1; i <= h; ++i) {
  37. for(int j = 1; j <= w; ++j) {
  38. cin >> symb;
  39.  
  40. if (symb == '*')
  41. matrix[j][i] = 0;
  42. else
  43. matrix[j][i] = 1;
  44. }
  45. }
  46.  
  47. for(int i = 0; i <= h + 1; ++i) {
  48. matrix[0][i] = 0;
  49. //cout << matrix[0][i];
  50. }
  51. for(int i = 0; i <= h + 1; ++i) {
  52. matrix[w + 1][i] = 0;
  53. //cout << matrix[h + 1][i];
  54. }
  55. for(int i = 0; i <= w + 1; ++i) {
  56. matrix[i][0] = 0;
  57. //cout << matrix[i][0];
  58. }
  59. for(int i = 0; i <= w + 1; ++i) {
  60. matrix[i][h + 1] = 0;
  61. //cout << matrix[i][w + 1];
  62. }
  63.  
  64. if(dfs(x1, y1)) {
  65. cout << "YES" << "\n";
  66. path.push_back({x1, y1});
  67. reverse(path.begin(), path.end());
  68. for (auto x : path)
  69. cout << x.first << " " << x.second << " ";
  70. }
  71. else cout << "NO" << "\n";
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement