ann8497

Laughhing bomb samsung

Sep 16th, 2019
2,277
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. /* laughing bomb
  2. INDEXING IS 1 BASED SO ARE THE INPUTS
  3.  
  4. INPUTS
  5. 2
  6. 7 8
  7. 0 0 1 1 0 0 0
  8. 1 1 1 1 0 1 0
  9. 0 0 1 1 1 1 1
  10. 0 1 1 1 1 1 1
  11. 0 1 0 0 1 1 0
  12. 0 1 1 1 1 0 0
  13. 0 0 1 0 1 1 1
  14. 0 0 0 0 1 0 0
  15. 2 5
  16. 10 10
  17. 1 1 1 1 0 1 1 0 0 0
  18. 0 1 1 1 1 1 0 1 1 0
  19. 0 0 1 1 0 1 0 1 1 1
  20. 0 1 1 1 1 1 0 0 1 1
  21. 0 1 0 1 0 1 1 1 1 0
  22. 0 0 0 0 0 1 1 0 0 0
  23. 1 0 1 0 1 0 1 1 0 0
  24. 0 0 1 1 1 1 1 1 1 1
  25. 1 0 1 0 0 1 0 1 1 0
  26. 1 1 1 0 0 0 0 1 1 1
  27. 2 2
  28.  
  29. OUTPUTS
  30. 8
  31. 21
  32.  
  33. */
  34. #include<iostream>
  35. using namespace std;
  36.  
  37. struct node{
  38.   int x;
  39.   int y;
  40.   int l;
  41. };
  42.  
  43. int sx,sy;
  44. node q[100000];
  45. bool vis[1000][1000];
  46. int front,back;
  47. int n,m;
  48. int a[100][100];
  49. int ans;
  50.  
  51. void init(){
  52.     front = back = 0;
  53. }
  54. void push(int x, int y, int l){
  55.     q[back].x = x;
  56.     q[back].y = y;
  57.     q[back].l = l;
  58.     back++;
  59. }
  60. node pop(){
  61.     return q[front++];
  62. }
  63. bool empty(){
  64.     return front == back;
  65. }
  66.  
  67. bool valid(int x, int y){
  68.     return (x>=0 && x<n && y>=0 && y<m && !vis[x][y]);
  69. }
  70.  
  71. int dx[] = {-1,0,1,0};
  72. int dy[] = {0,1,0,-1};
  73.  
  74.  
  75. void solve(){
  76.    
  77.     if(a[sx][sy] == 0)return;
  78.    
  79.     vis[sx][sy] = true;
  80.     push(sx,sy,1);
  81.  
  82.    
  83.     while(!empty()){
  84.        
  85.         node temp = pop();
  86.        
  87.         int x,y,l;
  88.         x = temp.x;
  89.         y = temp.y;
  90.         l = temp.l;
  91.        
  92.        
  93.         ans = max(ans,l);
  94.        
  95.        
  96.         for(int i = 0; i<4; i++){
  97.            
  98.             int xx = x + dx[i];
  99.             int yy = y + dy[i];
  100.            
  101.             if(valid(xx,yy) && a[xx][yy] == 1){
  102.                 vis[xx][yy] = true;
  103.                 push(xx,yy,l+1);
  104.             }
  105.            
  106.         }
  107.        
  108.     }
  109.  
  110. }
  111.  
  112. int main(){
  113.    
  114.     int t; cin>>t;
  115.     while(t--){
  116.        
  117.         /* FIRST COLUMN IS TAKEN AS INPUT AND THEN ROW ACC. TO TEST CASES */
  118.         cin>>m>>n;
  119.        
  120.        
  121.         for(int i =0; i<n;i++){
  122.             for(int j = 0; j<m; j++){
  123.                 vis[i][j] = false;
  124.                 cin>>a[i][j];
  125.             }
  126.         }
  127.         /* acc to the test cases first col is taken as input and then row
  128.            I have taken the input as row and then col so write it down as
  129.            cin>>sy>>sx
  130.         */
  131.         cin>>sx>>sy;
  132.         sx--; sy--;  /* zero based indexing */
  133.         init();
  134.         ans = -1;
  135.         solve();
  136.         cout<<ans<<endl;
  137.     }
  138.    
  139.    
  140.     return 0;
  141. }
Add Comment
Please, Sign In to add comment