API tools faq
paste
ann8497

endoscope Samsung

ann8497
Jun 21st, 2019
1,879
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.03 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. potential errors overflow due to limited size of queue
  3. wrong implementation of queue
  4. pipes written wrongly
  5.  
  6. TEST CASES
  7.  
  8. 12
  9. 5  6  2  1  3
  10. 0  0  5  3  6  0
  11. 0  0  2  0  2  0
  12. 3  3  1  3  7  0
  13. 0  0  0  0  0  0
  14. 0  0  0  0  0  0
  15.  
  16. 5  6  2  2  3
  17. 0  0  5  3  6  0
  18. 0  0  2  0  2  0
  19. 3  3  1  3  7  0
  20. 0  0  0  0  0  0
  21. 0  0  0  0  0  0
  22.  
  23. 5  6  1  4  3
  24. 0  0  5  3  6  0
  25. 0  0  2  0  2  0
  26. 3  3  1  3  7  0
  27. 0  0  0  0  0  0
  28. 0  0  0  0  0  0
  29.  
  30. 5  6  1  2  3
  31. 0  0  5  3  6  0
  32. 0  0  2  0  2  0
  33. 3  3  1  3  7  0
  34. 0  0  0  0  0  0
  35. 0  0  0  0  0  0
  36.  
  37. 5  6  1  1  3
  38. 0  0  5  3  6  0
  39. 0  0  2  0  2  0
  40. 3  3  1  3  7  0
  41. 0  0  0  0  0  0
  42. 0  0  0  0  0  0
  43.  
  44. 5  6  1  1  0
  45. 0  0  5  3  6  0
  46. 0  0  2  0  2  0
  47. 3  3  1  3  7  0
  48. 0  0  0  0  0  0
  49. 0  0  0  0  0  0
  50.  
  51. 5  6  2  2  10
  52. 0  0  5  3  6  0
  53. 0  0  2  3  1  6
  54. 3  3  1  3  7  3
  55. 0  0  0  0  0  0
  56. 0  0  0  0  0  0
  57.  
  58. 5  6  1  5  10
  59. 0  0  5  3  6  0
  60. 0  0  2  3  1  6
  61. 3  3  1  3  7  3
  62. 0  0  0  0  0  0
  63. 0  0  0  0  0  0
  64.  
  65. 5 6 2 1 3
  66. 0 0 5 3 6 0
  67. 0 0 2 0 2 0
  68. 3 3 1 3 7 0
  69. 0 0 0 0 0 0
  70. 0 0 0 0 0 0
  71.  
  72. 5 6 2 2 6
  73. 3 0 0 0 0 3
  74. 2 0 0 0 0 6
  75. 1 3 4 1 3 1
  76. 2 0 2 0 0 2
  77. 0 0 4 3 1 1
  78.  
  79. 5 6 2 2 6
  80. 3 0 0 0 0 3
  81. 2 0 0 0 5 6
  82. 1 3 4 1 1 1
  83. 2 0 2 0 0 2
  84. 0 0 4 3 1 1
  85.  
  86. 50 50 0 0 20
  87. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  88. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  89. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  90. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  91. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  92. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  93. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  94. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  95. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  96. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  97. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  98. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  99. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  100. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  101. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  102. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  103. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  104. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  105. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  106. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  107. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  108. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  109. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  110. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  111. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  112. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  113. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  114. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  115. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  116. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  117. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  118. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  119. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  120. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  121. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  122. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  123. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  124. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  125. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  126. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  127. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  128. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  129. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  130. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  131. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  132. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  133. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  134. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  135. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  136. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  137.  
  138. OUTPUT
  139. 5
  140. 7
  141. 5
  142. 6
  143. -1
  144. -1
  145. 12
  146. 12
  147. 5
  148. 7
  149. 8
  150. 210
  151.  
  152. */
  153.  
  154. #include<iostream>
  155. using namespace std;
  156.  
  157. struct node{
  158.     int x;
  159.     int y;
  160.     int l;
  161. };
  162.  
  163. node q[1000000];
  164.  
  165. int front, back;
  166.  
  167. void init(){
  168.     front = back = 0;
  169. }
  170.  
  171. node pop(){
  172.     return q[front++];
  173. }
  174.  
  175. void push(int x, int y, int l){
  176.     q[back].x = x;
  177.     q[back].y = y;
  178.     q[back].l = l;
  179.     back++;
  180. }
  181.  
  182. bool empty(){
  183.     return front == back;
  184. }
  185.  
  186. int a[1000][1000];
  187. bool vis[1000][1000];
  188. int n,m,r,c,len;
  189. int ans;
  190.  
  191. void init2(){
  192.     for(int i = 0; i<1000; i++){
  193.         for(int j =0; j<1000; j++){
  194.             vis[i][j] = false;
  195.         }
  196.     }
  197. }
  198.  
  199. bool valid(int x, int y){
  200.     return (x>=0 && x<n && y>=0 && y<m && !vis[x][y]);
  201. }
  202.  
  203. void solve(){
  204.    
  205.     if(a[r][c] == 0)return;
  206.     ans = 1;
  207.    
  208.     vis[r][c] = true;
  209.     push(r,c,1);
  210.    
  211.     while(!empty()){
  212.        
  213.         node temp = pop();
  214.         int x = temp.x;
  215.         int y = temp.y;
  216.         int l = temp.l;
  217.        
  218.         // up 1 2 4 down 1 2 5 6  left 1 3 6 7 right 1 3 4 5
  219.        
  220.         //up jana h
  221.         if(valid(x-1,y) && l+1 <= len)
  222.             if(a[x-1][y] == 1  || a[x-1][y] ==2 || a[x-1][y] ==5 || a[x-1][y] ==6 )
  223.                 if(a[x][y] == 1 || a[x][y] == 2 || a[x][y] == 4 || a[x][y] == 7){
  224.                     vis[x-1][y] = true;
  225.                     push(x-1,y,l+1);
  226.                     ans++;
  227.                 }
  228.            
  229.         // down jana hai
  230.          if(valid(x+1,y) && l+1 <= len)
  231.             if(a[x+1][y] == 1  || a[x+1][y] ==2 || a[x+1][y] ==4 || a[x+1][y] ==7 )
  232.                 if(a[x][y] == 1 || a[x][y] == 2 || a[x][y] == 5 || a[x][y] == 6){
  233.                     vis[x+1][y] = true;
  234.                     push(x+1,y,l+1);
  235.                     ans++;
  236.                 }
  237.                
  238.         // left jana hai
  239.          if(valid(x,y-1) && l+1 <= len)
  240.             if(a[x][y-1] == 1  || a[x][y-1] ==3 || a[x][y-1] ==4 || a[x][y-1] ==5 )
  241.                 if(a[x][y] == 1 || a[x][y] == 3 || a[x][y] == 6 || a[x][y] == 7){
  242.                     vis[x][y-1] = true;
  243.                     push(x,y-1,l+1);
  244.                     ans++;
  245.                 }
  246.                
  247.           // right jana jai      
  248.          if(valid(x,y+1) && l+1 <= len)
  249.             if(a[x][y+1] == 1  || a[x][y+1] ==3 || a[x][y+1] ==6 || a[x][y+1] ==7 )
  250.                 if(a[x][y] == 1 || a[x][y] == 3 || a[x][y] == 4 || a[x][y] == 5){
  251.                     vis[x][y+1] = true;
  252.                     push(x,y+1,l+1);
  253.                     ans++;
  254.                 }
  255.            
  256.     }
  257.    
  258. }
  259.  
  260. int main(){
  261.    
  262.    
  263.     int t; cin>>t;
  264.     while(t--){
  265.  
  266.     cin>>n>>m>>r>>c>>len;
  267.    
  268.     for(int i =0; i<n; i++){
  269.         for(int j =0; j<m; j++){
  270.             cin>>a[i][j];
  271.         }
  272.     }
  273.    
  274.      
  275.      init();
  276.      init2();
  277.      
  278.     ans = -1;
  279.     solve();
  280.     cout<<ans<<endl;
  281.    
  282.     }
  283.     return 0;
  284. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!