kolbka_

Untitled

Jan 20th, 2022
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.84 KB | None | 0 0
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11. #include <iostream>
  12. #include <cassert>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <unordered_map>
  16. #include "optimization.h"
  17. #include <map>
  18. #include <unordered_set>
  19.  
  20. #define all(a) a.begin(), a.end()
  21. using namespace std;
  22. vector<vector<int>> mark;
  23. vector<vector<int>> matrix;
  24. bool flag = false;
  25. int n;
  26. int m;
  27. vector<pair<int,int>> result;
  28. pair<int,int> finish;
  29. vector<pair<int,int>> w = {{1, 0}, {0,1}, {-1, 0}, {0, -1}};
  30. void dfs(pair<int,int> start) {
  31. result.push_back(start);
  32. if (start == finish) {
  33. flag = true;
  34. return;
  35. }
  36. mark[start.first][start.second] = 1;
  37. for (auto [x,y] : w){
  38. int f1 = x + start.first;
  39. int f2 = y + start.second;
  40. if (!flag && f1 >= 0 && f1 < m && f2 >= 0 && f2 < n && matrix[f1][f2] != -1 && mark[f1][f2] == 0){
  41. dfs({f1,f2});
  42. }
  43. }
  44. if (flag){
  45. return;
  46. }
  47. result.pop_back();
  48. }
  49.  
  50. int main() {
  51. // cin >> n >> m;
  52. n = readInt(); m = readInt();
  53. int a,b;
  54. // cin >> a >> b;
  55. a = readInt(); b = readInt();
  56. pair<int,int> start = {b-1,a-1};
  57. // cin >> a >> b;
  58. a = readInt(); b = readInt();
  59. finish = {b-1,a-1};
  60. matrix.resize(m, vector<int>(n, -1));
  61. mark.resize(m, vector<int>(n, 0));
  62. for (int i = 0; i < m; i++){
  63. for (int j = 0; j < n; j++){
  64. char a = readChar();
  65. // cin >> a;
  66. if (a == '.'){
  67. matrix[i][j] = 0;
  68. }
  69. }
  70. }
  71. dfs(start);
  72. if (flag){
  73. // cout << "YES\n";
  74. writeWord("YES\n");
  75. for (auto [x,y] : result){
  76. // cout << y+1 << " " << x + 1 << endl;
  77. writeInt(y+1, ' ');
  78. writeInt(x + 1, '\n');
  79. }
  80. }
  81. else{
  82. // cout << "NO\n";
  83. writeWord("NO\n");
  84. }
  85. }
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
Advertisement
Add Comment
Please, Sign In to add comment