Water Flow

https://www.interviewbit.com/old/problems/water-flow/

 int n,m;
void dfs(int i,int j,vector<vector<int> > &A,vector<vector<int> > &b) // b is the visited array
{
    if(b[i][j]==0) b[i][j]=1;
    if(i>0 && A[i-1][j]>=A[i][j] && b[i-1][j]==0) dfs(i-1,j,A,b);
    if(j>0 && A[i][j-1]>=A[i][j] && b[i][j-1]==0)  dfs(i,j-1,A,b);
    if(j<m-1 && A[i][j+1]>=A[i][j] && b[i][j+1]==0) dfs(i,j+1,A,b);
    if(i<n-1 && A[i+1][j]>=A[i][j] && b[i+1][j]==0) dfs(i+1,j,A,b);
    return;
    
}
int Solution::solve(vector<vector<int> > &A) {
    n=A.size();
     m=A[0].size();
    vector<vector<int> > blue(n,vector<int> (m,0));
    vector<vector<int> > red(n,vector<int> (m,0));
    for(int i=0;i<m;i++) dfs(0,i,A,blue);
    for(int i=1;i<n;i++) dfs(i,0,A,blue);
    for(int i=0;i<n;i++) dfs(i,m-1,A,red);
    for(int i=m-2;i>=0;i--) dfs(n-1,i,A,red);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(blue[i][j]==1 && red[i][j]==1) ans++;
        }
    }
    
    return ans;
}

Comments

Post a Comment

Popular posts from this blog

Perfect Peak of Array

  Given an integer array A of size N . You need to check that whether there exist a element which is strictly greater than all the elements on left of it and strictly smaller than all the elements on right of it. If it exists return 1 else return 0 .  https://www.interviewbit.com/old/problems/perfect-peak-of-array/ int Solution::perfectPeak(vector<int> &A) { int ans=-1; int l[A.size()]; int r[A.size()]; l[0]=A[0]; r[A.size()-1]=A[A.size()-1]; for(int i=1;i<A.size();i++){     l[i] = max(A[i],l[i-1]); } for(int i=A.size()-2;i>=0;i--){     r[i] = min(A[i],r[i+1]); } for(int i=1;i<A.size()-1;i++){     if(A[i]>l[i-1]&&A[i]<r[i+1]){         return 1;     } } if(ans==-1){     return 0; } }  
Read more

Is Rectangle?

 https://www.interviewbit.com/old/problems/is-rectangle/ int Solution::solve(int A, int B, int C, int D) {      if (((A==B)&&(C==D))||((A==C)&&(B==D))||((A==D)&&(B==C))){         return 1;     }else{         return 0;     } }  
Read more

Sort array with squares!

 https://www.interviewbit.com/old/problems/sort-array-with-squares/      vector<int> Solution::solve(vector<int> &arr) {         int mid=0;     for(int i=0;i<arr.size();i++)     {         if(arr[i]>=0)         {             mid=i;             break;         }     }     int i=mid-1,j=mid;     vector<int>res(arr.size());     int k=0;     while(i>=0 && j<arr.size())     {         if((arr[i]*arr[i])<(arr[j]*arr[j]))         {             res...
Read more