Advertisement
Guest User

Untitled

a guest
Jan 24th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.80 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. int N, K;
  10.  
  11. string lwall, rwall;
  12. bool Visited[2][200005];
  13.  
  14. bool check(bool wall, int height)
  15. {
  16. if(wall == 0)
  17. return lwall[height] != 'X';
  18.  
  19. else
  20. {
  21. return rwall[height] != 'X';
  22. }
  23. return false;
  24. }
  25.  
  26.  
  27. void bfs()
  28. {
  29. queue < pair < bool , int > > Q; // SOL = 0 , SAG = 1
  30. Q.push( make_pair ( 0, 1 ) );
  31. Visited[0][1] = true;
  32.  
  33. bool possible = false;
  34. bool wall;
  35. int height;
  36. while(!Q.empty())
  37. {
  38. wall = Q.front().first;
  39. height = Q.front().second;
  40. Q.pop();
  41.  
  42. cout << wall << " " << height << endl;
  43.  
  44. if(height >= N)
  45. {
  46. possible = true;
  47. break;
  48. }
  49.  
  50. if(Visited[wall][height+1] == 0)
  51. {
  52. if(check(wall,height+1))
  53. {
  54. Q.push( make_pair (wall, height+1) );
  55. Visited[wall][height+1] = true;
  56. }
  57. }
  58. if(height-1 > 0 && Visited[wall][height-1] == 0)
  59. {
  60. if(check(wall,height-1))
  61. {
  62. Q.push( make_pair (wall, height-1) );
  63. Visited[wall][height-1] = true;
  64. }
  65. }
  66.  
  67. if(Visited[1-wall][height+K] == 0)
  68. {
  69. if(check(1-wall,height+K))
  70. {
  71. Q.push( make_pair (1-wall, height+K) );
  72. Visited[1-wall][height+K] = true;
  73. }
  74. }
  75. }
  76.  
  77. if(possible)
  78. cout << "YES" << endl;
  79. else
  80. cout << "NO" << endl;
  81.  
  82. }
  83.  
  84. int main() {
  85.  
  86. cin >> N >> K;
  87. cin >> lwall >> rwall;
  88. lwall = '.' + lwall;
  89. rwall = '.' + rwall;
  90. bfs();
  91.  
  92. return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement