Advertisement
Korotkodul

ОИ-2 bfs лабиринт

Jan 14th, 2022 (edited)
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17. for (auto x: v) cout<<x<<' ';
  18. cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22. for (auto x: v) cout<<x<<' ';
  23. cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28. for (auto x: v) cv(x);
  29. cout<<"\n";
  30. }
  31.  
  32.  
  33. vector < vector < vector<pii> > > G;
  34. //vector[0] - слева - пара (x,y)
  35. //vec[1] - справа
  36. //vec[2] - сверху
  37. //vec[3] - снизу
  38. vector <vector<int>> dsk;
  39. vector <vector <int> > dist;
  40.  
  41. const int inf = 2e9;
  42.  
  43. int n,m;
  44. bool gd(pii x){
  45. return x.first >= 0 && x.first < n && x.second >= 0 && x.second < m && dsk[x.first][x.second] != 1;
  46. }
  47.  
  48. void shG(){
  49. for (int i=0;i<n;++i){
  50. for (int j=0;j<m;++j){
  51. cout<<"("<<i<<","<<j<<") \n";
  52. for (int k = 0;k<4;++k){
  53. cout<<G[i][j][k].first<<' '<<G[i][j][k].second<<"\n";
  54. }
  55. }
  56.  
  57. }cout<<"\n";
  58. }
  59.  
  60. void shdsk(){
  61. for (int i=0;i<n;++i){
  62. for (int j=0;j<m;++j){
  63. cout<<dsk[i][j]<<' ';
  64. }cout<<"\n";
  65. }cout<<"\n";
  66. }
  67.  
  68. int main()
  69. {
  70. ios::sync_with_stdio(0);
  71. cin.tie(0);
  72. cout.tie(0);
  73.  
  74. //cin>>n>>m;
  75. n = 18;
  76. m = 14;
  77. dist.resize(n, vector <int> (m , inf));
  78. dsk.resize(n, vector <int>(m,0));
  79. for (int i=0;i<n;++i){
  80. for (int j=0;j<m;++j) continue ;//cin>>dsk[i][j];
  81. }
  82. //строим G
  83. for (int i = 1; i <= 7;++i) dsk[i][0] = 1;
  84. for (int j = 5; j<=9;++j) dsk[0][j] = 1;
  85. for (int i=0;i<=7;++i) dsk[i][7] = 1;
  86. for (int i = 1;i<=3;++i) dsk[i][10] =1;
  87. for (int j = 1;j<=6;++j) dsk[9][j] = 1;
  88. for (int i=5;i<=9;++i) dsk[i][10] = 1;
  89. for (int j=8;j<=10;++j) dsk[9][j] = 1;
  90. for (int i=4;i<=8;++i) dsk[i][12] = 1;
  91. for (int j=3;j<=4;++j) dsk[13][j] = 1;
  92. vector <pii> pnt = { {14, 2}, {14, 5}, {15, 4}, {16, 6}, {12, 12}, {13, 11}, {14, 10}, {15, 9}, {15, 12}, {16, 11} };
  93. for (int i=0;i<pnt.size();++i){
  94. dsk[pnt[i].first][pnt[i].second] = 1;
  95. }
  96. shdsk();
  97. G.resize(n, vector <vector <pii> > (m, vector <pii> (4, {-1, -1})));
  98. pii str = {0,0};
  99. pii v = str;
  100. //заполняем v[1] и v[3] для (0,0)
  101. while (gd({v.first, v.second+1})){
  102. v.second++;
  103. if (dsk[v.first][v.second] == 2){
  104. cout<<1<<"\n";
  105. exit(0);
  106. }
  107. }
  108. G[0][0][1] = v;
  109. G[v.first][v.second][0] = {0,0};
  110.  
  111. v = str;
  112. while (gd({v.first+1, v.second})){
  113. v.first++;
  114. if (dsk[v.first][v.second] == 2){
  115. cout<<1<<"\n";
  116. exit(0);
  117. }
  118. }
  119.  
  120. G[0][0][3] = v;
  121. G[v.first][v.second][2] = {0,0};
  122. //vector[0] - слева
  123. //vec[1] - справа
  124. //vec[2] - сверху
  125. //vec[3] - снизу
  126. shG();
  127.  
  128. //план такой: сначала отметить ребра от (0,0) до 2-х доступных точек (вершин) - OK
  129. //потом отметить расстояния от всех получившихся (2-х - 3-х вершин) ребра до остальных доступных точек (КАК - это надо додоумать)
  130. //запуститься из (0,0)
  131.  
  132. }
  133. /*
  134. 4 5
  135. 0 0 0 0 1
  136. 0 1 1 0 2
  137. 0 2 1 2 0
  138. 0 0 1 0 0
  139. */
  140.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement