Guest User

CHEFARC.cpp

a guest
Jan 25th, 2021
36
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define REP(i,a,b) for(int i=a;i<b;i++)
  4. #define vi vector<int>
  5. #define vvi vector<vi>
  6.  
  7.  
  8. void printGrid(vvi mat){
  9.     cout<<"GRID:\n";
  10.     for(auto ele:mat){
  11.         for(auto every:ele){
  12.             cout<<every<<" ";
  13.         }
  14.         cout<<endl;
  15.     }
  16. }
  17.  
  18.  
  19.  
  20. bool isValid(int R,int C,int r,int c){
  21.     return r>=0&&r<R&&c>=0&&c<C;
  22. }
  23.  
  24. void bfs(vvi mat,int R,int C,int sX,int sY,vvi&grid,int k){
  25.     vvi move={
  26.         {1,1},
  27.         {-1,1},
  28.         {1,-1},
  29.         {0,1},
  30.         {1,0},
  31.         {0,-1},
  32.         {-1,0},
  33.         {-1,-1}
  34.     };
  35.  
  36.     vvi vis(R,vi(C,0));
  37.  
  38.     deque<pair<int,int>>Q;
  39.     Q.push_back({sX,sY});
  40.     vis[sX][sY]=1;
  41.     grid[sX][sY]=0;
  42.  
  43.     while(!Q.empty()){
  44.  
  45.         int x=Q.front().first;
  46.         int y=Q.front().second;
  47.         Q.pop_front();
  48.  
  49.  
  50.         for(auto ele:move){
  51.             int beginX=x;
  52.             int beginY=y;
  53.             int start=0;
  54.  
  55.  
  56.              int prevX=beginX;
  57.              int prevY=beginY;
  58.            
  59.             while(1){
  60.                 prevX=beginX;
  61.                 prevY=beginY;
  62.                 beginX=beginX+ele[0];
  63.                 beginY=beginY+ele[1];
  64.                
  65.  
  66.                 if(isValid(R,C,beginX,beginY)){
  67.                     if(vis[beginX][beginY]==0 && ( abs(beginX-x)+abs(beginY-y)<=k ) && mat[beginX][beginY]==0){
  68.                         vis[beginX][beginY]=1;
  69.                         grid[beginX][beginY]=grid[x][y]+1;
  70.                         Q.push_back({beginX,beginY});
  71.                        
  72.                     }
  73.                 }
  74.                 else{
  75.                     break;
  76.                 }
  77.  
  78.             }
  79.  
  80.             // if(prevX!=x||prevY!=y){
  81.             //             Q.push_back({prevX,prevY});
  82.                        
  83.             // }
  84.                    
  85.  
  86.         }
  87.  
  88.    
  89.     }
  90.  
  91. }
  92.  
  93. int main(){
  94.     int t;
  95.     cin>>t;
  96.  
  97.     while(t--){
  98.         int n,m,k1,k2;
  99.         cin>>n>>m>>k1>>k2;
  100.  
  101.        
  102.         vvi mat(n,vi(m,0));
  103.        
  104.         vvi grid1(n,vi(m,INT_MAX));
  105.         vvi grid2(n,vi(m,INT_MAX));
  106.  
  107.         int i;
  108.         REP(i,0,n){
  109.             int j;
  110.             REP(j,0,m){
  111.                 int ele;
  112.                 cin>>ele;
  113.                 mat[i][j]=ele;
  114.             }
  115.         }
  116.  
  117.         // R1 is at (0,0)
  118.  
  119.         bfs(mat,n,m,0,0,grid1,k1);
  120.         //printGrid(grid1);
  121.  
  122.        
  123.         // R2 is at (0,m-1)
  124.        
  125.        
  126.         bfs(mat,n,m,0,m-1,grid2,k2);
  127.  
  128.         //printGrid(grid1);
  129.         //printGrid(grid2);
  130.  
  131.         vvi finalGrid(n,vi(m,0));
  132.  
  133.         REP(i,0,n){
  134.             int j;
  135.             REP(j,0,m){
  136.                 if(grid1[i][j]==INT_MAX||grid2[i][j]==INT_MAX){
  137.                     finalGrid[i][j]=INT_MAX;
  138.                 }
  139.                 else{
  140.                     finalGrid[i][j]=max(grid1[i][j],grid2[i][j]);
  141.  
  142.                 }
  143.             }    
  144.         }
  145.  
  146.         //printGrid(finalGrid);
  147.         int ans=INT_MAX;
  148.         REP(i,0,n){
  149.             int j;
  150.             REP(j,0,m){
  151.                 if(finalGrid[i][j]!=INT_MAX){
  152.                     ans=min(ans,finalGrid[i][j]);
  153.                 }
  154.             }
  155.         }
  156.  
  157.         if(ans==INT_MAX)ans=-1;
  158.         cout<<ans<<endl;
  159.  
  160.     }
  161.  
  162.     return 0;
  163. }
RAW Paste Data